stumped stumped - 7 months ago 23
Java Question

Confusion on quicksort that takes logarithmic space

If only the smaller partitioned array is being called how is the larger one sorted? I only see code to change the position of

b
if done recursively (
QS
called in
if
and
else
statement).

public static void QS(int[] b, int h, int k) {
int h1= h; int k1= k;
// invariant b[h..k] is sorted if b[h1..k1] is sorted
while (b[h1..k1] has more than 1 element) {
int j= partition(b, h1, k1);
// b[h1..j-1] <= b[j] <= b[j+1..k1]
if (b[h1..j-1] smaller than b[j+1..k1])
QS(b, h, j-1); h1= j+1;
else
QS(b, j+1, k1); k1= j-1;
}
}

Answer

That is some hard to read psuedo-code. This might be a bit easier to understand:

QuickSort(b[], low, hi)
  while the range low..hi contains more than 1 element
    1: Pick a random pivot 'j' from the array
    2: Re-order the array so that all elements less than the pivot are in
       b[low..j-1], and all elements greater than the pivot are in b[j+1..hi]
    3: Call quicksort on the side with less elements, and update the range to
       exclude the sorted side

Roughly half of the values will be less than the pivot, and half of the values will be greater than the pivot. This means that after step 3, the size of the range low..hi has roughly halved. Thus, it takes log|N| iterations before the range contains only one element.

It's hard to explain this bit, but see how step 3 only calls QuickSort on one half of the array? It's because the remainder of the while-loop sorts the other half. The function could easily be re-written as the following:

QuickSort(b[], low, hi)
  if the range low..hi contains more than 1 element
    1: Pick a random pivot 'j' from the array
    2: Re-order the array so that all elements less than the pivot are in
       b[low..j-1], and all elements greater than the pivot are in b[j+1..hi]
    3: Call quicksort on both sides

The while-loop has been replaced by an if statement and a second recursive call. I hope from here that you can see the complexity is roughly N log|N|.

Edit

So how does the while-loop sort the remaining elements? After step 3, the range has been updated to exclude the smaller half, because we just sorted it with a call to QuickSort. This means that the range now only contains the larger half - the unsorted elements. So we repeat steps 1 - 3 on these unsorted elements, and update the range again.

The number of unsorted elements gets smaller and smaller with every iteration, and eventually we will be left with only one unsorted element. But of course, one element on its own is sorted, so at this point we know we have sorted every element in the array.