Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

permalink.gmane.org

Post reply on HN
Print view View original

1–10 of 17 posts

Re: Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

#3

Post by fhars »

alexh wrote: post #2

I read the documentation he linked to. It seems odd to me that there was no mention of a N-Pivot quicksort. Unless I missed it. It seems like the burden would be on proving that 2 was the optimal value of N

With two pivots, you can start the partitioning at either end and have a well defined location for each of the three partitions (at the top, at the botton, and inbetween). With more than three partitions, you would not know where to put the second to second last border without first sorting the array. You could just guess, but that would probably result in quite a lot of additional array shifting (lucky if you have a dedicated blitter chip for that :-)).

Re: Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

#4

Post by GrandMasterBirt »

alexh wrote: post #2

I read the documentation he linked to. It seems odd to me that there was no mention of a N-Pivot quicksort. Unless I missed it. It seems like the burden would be on proving that 2 was the optimal value of N

Having N > 2 will require you to do a sort on the pivots :P Also you will require that the array size be at least N. N = 2 is a perfect size --

size = 0 -> no sort

size = 1 -> no sort

size = 2 -> pivots can be made, thus can be sorted

etc.

Re: Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

#6

Post by iclelland »

GrandMasterBirt wrote: post #4
alexh wrote: post #2

I read the documentation he linked to. It seems odd to me that there was no mention of a N-Pivot quicksort. Unless I missed it. It seems like the burden would be on proving that 2 was the optimal value of N

Having N > 2 will require you to do a sort on the pivots :P Also you will require that the array size be at least N. N = 2 is a perfect size -- size = 0 -> no sort size = 1 -> no sort size = 2 -> pivots can be made, thus can be sorted etc.

Having N > 1 requires you to do a sort on the pivots. From the algorithm:

  3. P1 must be less than P2, otherwise they are swapped.

Re: Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

#9

Post by gjm11 »

sanj wrote: post #7

Any insights into the "fat pivot" problem?

I thought "fat pivot" meant the approach to quicksort where you partition into { smaller, equal, larger } and then sort the three subarrays instead of two. I'm not sure what the "fat pivot problem" would be. Anyway, this new approach is a generalization of that -- fat pivoting is the special case where the two pivots are equal.

Re: Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot

#10

Post by gjm11 »

alexh wrote: post #2

I read the documentation he linked to. It seems odd to me that there was no mention of a N-Pivot quicksort. Unless I missed it. It seems like the burden would be on proving that 2 was the optimal value of N

You can make a quicksortish sort algorithm with N log N worst case by letting the number of pivots increase with N. (Details and proof, of course, in Knuth. The details are nontrivial but not all that painful.) I don't think anyone's ever proposed that that's worth doing in practice.

Using more pivots is going to make the code more complicated. The benefits of moving from one pivot to two seem to be real but not enormous; I'd be pretty surprised if moving to three pivots produced benefits worth the cost. But of course that's just handwaving, and indeed it would be interesting to measure.

Post reply on HN