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 atRight-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
