Worst-case performance of quickSort / getPivot

[Jean Christophe]

On Saturday, 16 November 2013 at 16:10:56 UTC, Andrei 
Alexandrescu wrote:
> On 11/16/13 6:20 AM, Jean Christophe wrote:
>> On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir 
>> Panteleev wrote:
>>
>>> getPivot(0..10)
>>> 8,7,6,5,4,3,2,1,0,9 <- getPivot - before swap
>>> 9,7,6,5,4,8,2,1,0,3 <- getPivot - after swap
>>> 9,7,6,5,4,3,2,1,0,8 <- quickSortImpl - after swap
>>> 9,8,6,5,4,3,2,1,0,7 <- quickSortImpl - after partition
>>> getPivot(2..10)
>>> 6,5,4,3,2,1,0,7 <- getPivot - before swap
>>> 7,5,4,3,6,1,0,2 <- getPivot - after swap
>>> 7,5,4,3,2,1,0,6 <- quickSortImpl - after swap
>>> 7,6,4,3,2,1,0,5 <- quickSortImpl - after partition
>>> (...)
>>
>> One possible implementation suggests to swap Left and Right 
>> immediatly
>> after choosing the Pivot (if Left > Right), then place the 
>> Pivot at
>> Right-1. It seems that this option was not taken. Any reason?
>
> That may help this particular situation, but does it do 
> anything interesting in general?

Yes. This has the extra advantage that the smallest of the three 
winds up in A[left], which is where the partitioning routine 
would put it anyway. The largest winds up at A[right] which is 
also the correct place, since it is larger than the Pivot. 
Therefore you can place the Pivot in A[right -1] and initialize i 
and j to (left+1) and (right-2) in the partition phase. Another 
benefit is that because A[left] is smaller than the Pivot, it 
will act as a sentinel for j. We do not need to worry about j 
running past the end. Same for i. Thus you assert:

A[left] <= A[center] <= A[right]

even before you hide the Pivot.

-- JC