Why the different ways of calling quicksort recursively?

Question

I've noticed a discrepancy in the way quicksort is called recursively.

One way is

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x-1)
  quicksort(Array, x+1, right)



  partition(array, left, right)
     pivotIndex := choose-pivot(array, left, right)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]
     storeIndex := left
     for i from left to right - 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

[EXAMPLE]

This makes sense because quicksort works by partitioning the other elements around the pivot so the element Array[x] should be in its final position. Therefore the range [left, partion-1] and [partition+1, right] remains.

The other way

quicksort(Array, left, right)
  x = partition(Array, left, right)
  quicksort(Array, left, x)
  quicksort(Array, x+1, right)

PARTITION(A,p,r)

x  A[p]    
i  p - 1    
j  r + 1   
while TRUE  
   do repeat j  j - 1   
        until A[j]  x   
      repeat i  i + 1    
        until A[i]  x    
      if i < j    
          then exchange A[i]  A[j]
          else return j

[EXAMPLE]

Notice the -1 is missing. These seems to suggest that the array was partitioned correctly but no single element is in its final position. These two ways are not interchangeable, if I put in a -1 in the second way an input array is improperly sorted.

What causes the difference? Obviously it's somewhere in the partition method, does it have to do with Hoare's or Lumuto's algorithm was used?

Cowling

Answer 1

There is not actually that much difference in efficiency between the two versions, except when operating on the smallest arrays. The majority of the work is done in separating one large array of size n, whose values can be at many as n spaces away from their proper positions, into two smaller arrays which, being smaller, cannot have values as far displaced from their proper positions, even in the worst case. The "one way" essentially creates three partitions at each step - but since the third one is just one space large, it only makes an O(1) contribution towards the progress of the algorithm.

That being said, it's very easy to implement that final switch, so I'm not sure why the code of your "other way" example doesn't take that step. They even point out a pitfall (if the last rather than the first element is chosen for the pivot, the recursion never ends) which would be avoided entirely by implementing that switch that eliminates the pivot element at the end. The only situation I can imagine where that would be the preferable code to use would be where code space was at an absolute premium.

Ingenue

Answer 2

If nothing else, excluding or passing the partition index might be the difference between closed and half-open intervals: right might be the first index not to touch - no telling from incomplete snippets without references.

Hesychast

Answer 3

The difference is caused because the return value of partition() means different things.

• In One way, the return value of partition() is where the pivot that was used for the partition ended up in i.e. Array[x] after parition() is the pivot that was used in partition().
• In Other way, the return value of partition() is NOT where the pivot that was used for the partition ended up in i.e. Array[x] after partition() is an element that was less than the pivot that was used in partition(), but we don't know much other than that. The actual pivot could be located anywhere in the upper half of the array.

From this it follows that the first recursive call with x-1 instead of x in the Other way could quite easily give incorrect results e.g. pivot = 8, Array[x] = 5 and Array[x-1] = 7.

Bronder

Answer 4

If you think about it, the other way would not make any difference to the algorithm. If the partition algorithm is the same as in the first one, then including the pivot in one of the sub-arrays would not have any effect, since in that case none of the other elements would swap its place with the pivot in the sub array.

At most it would increase the number of comparisons by some number. Although I'm unsure if it would adversely affect the sorting time for large arrays.

Ratio