CODEWITHSUNDEEP
javaalgorithmsortingbig-oquicksort
stumped
stumped

Reputation: 3293

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; 
     }
}

Upvotes: 1

Views: 78

Answers (2)

rcgldr
rcgldr

Reputation: 28828

Note after the recursive call to QS, h1 is is updated if b[h1..] was smaller than b[j+1..] and k1 is updated if if b[h1..] was greater or equal to b[j+1..] .

There's a bug in the code, the first call after the if should be QS(b, h1, j-1);

Logarithmic space usage is referring to the stack space used by quicksort due to recursion. In the example code, only the smaller partition is sorted with a recursive call, then the code loops back to split up the larger partition into two parts, and again, only use a recursive call for the smaller part of the now split up larger partition.

Link to articles:

http://en.wikipedia.org/wiki/Quicksort#Optimizations

http://blogs.msdn.microsoft.com/devdev/2006/01/18/efficient-selection-and-partial-sorting-based-on-quicksort

I'm not sure about the reference to tail recursion, since the code includes an actual loop instead of using tail recursion. Tail recursion would look like a recursive call on the last line to be executed in a function, where a compiler can optimize it into a loop.

Upvotes: 1

Andrew Williamson
Andrew Williamson

Reputation: 8696

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.

Upvotes: 1

Related Questions