What's the difference of dual pivot quick sort and quick sort?

Question

I've never seen dual pivot quick sort before. Is it an upgraded edition of quick sort?
And what is the difference between dual pivot quick sort and quick sort?

Melamie

Thank you very much .I got the right answer. – Melamie

@GregHewgill Thank you very much .I got the right answer. – Melamie

@GregHewgill When I had this question and searched Google, it brought me here. I'm sure glad Brutal_JL asked this question and other people actually answered it! :) – Akron

Answer 1

I find this in the Java doc.

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Then I find this in the Google search result. Theory of quick sort algorithm:

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot element is in its final position.
3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements.

In comparison, dual-pivot quick sort:

1. For small arrays (length < 17), use the Insertion sort algorithm.
2. Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.
3. P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
   • part I with indices from left+1 to L–1 with elements, which are less than P1,
   • part II with indices from L to K–1 with elements, which are greater or equal to P1 and less or equal to P2,
   • part III with indices from G+1 to right–1 with elements greater than P2,
   • part IV contains the rest of the elements to be examined with indices from K to G.
4. The next element a[K] from the part IV is compared with two pivots P1 and P2, and placed to the corresponding part I, II, or III.
5. The pointers L, K, and G are changed in the corresponding directions.
6. The steps 4 - 5 are repeated while K ≤ G.
7. The pivot element P1 is swapped with the last element from part I, the pivot element P2 is swapped with the first element from part III.
8. The steps 1 - 7 are repeated recursively for every part I, part II, and part III.

Melamie

And this is why we are extremely grateful to the Java Library designers that we don't have to implement our own sorting algorithms, otherwise we'd all be using bubble sort ;-) – Restive

After step 7 and before step 8, P1 can be compared to P2. If they are the same value, it means part II need not be sorted, they are duplicates of P1 and P2. – Wolters

Why 17 for insertion sort. Is it arbitrary? – Corrugate

@Melamie but what if pivots are equal? – Faa

@abksrv, MergeSort is O(n log n) and InsertionSort is O(n^2), however this is really C1 * n * log(n) and C2 * n * n (where C1 and C2 are some constants). When n is large, the constants are irrelevant. When n is small they can be relevant. Presumably the implementors investigated and found that 17 is the tipping point where: C1 * log(17) > C2 * 17, but C1 * log(18) < C2 * 18. – Under

Yaroslovsky's original paper (codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf) sets 27, not 17, as the threshold for using insertion sort. On the other hand, the implementation in Java 8 by Yaroslovsky, Bentley, and Bloch (hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/…) uses 47 as the threshold. – Balance

Without switching to Insertion sort at a point, is the procedure about the same as Dijkstra’s original 3-way partitioning? – Numerate

Optimized version by Yaroslovsky recently merged to OpenJDK - bugs.openjdk.java.net/browse/JDK-8226297 – Fico

Answer 2

I just want to add that from the algorithm point of view (i.e. the cost only considers the number of comparisons and swaps), 2-pivot quicksort and 3-pivot quicksort is not better than classical quicksort (which uses 1 pivot), if not worse. However, they are faster in practice since they take the benefits of modern computer architecture. Specifically, their numbers of cache misses are smaller. So if we remove all caches and there are only CPU and main memory, in my understanding, 2/3-pivot quicksort is worse than classical quicksort.

References: 3-pivot Quicksort: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 Analysis of why they perform better than classical Quicksort: https://arxiv.org/pdf/1412.0193v1.pdf A complete and not-too-much-details reference: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf

So

Profound answer. Probably the best one here. The last link is outdated. By any chance do you still have the file? – Dasilva

You can find all the updated lectures here: algs4.cs.princeton.edu/lectures – Gatefold

Answer 3

For those who are interested, take a look how they implemented this algorithm in Java:

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%2Cint%5B%5D%2Cint%2Cint%29

As stated in source:

"Sorts the specified range of the array using the given workspace array slice if possible for merging

The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations."

Gingrich

You can also browse the code from the following liks : codatlas.com/github.com/lambdalab-mirror/jdk7u-jdk/master/src/… github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/… – Hornback