What is the difference in quick sorting and quick sorting of a double hinge?

Question

I had never seen a double turn before. Should this be a quick sort update version?
And what is the difference between quick sort and quick double step sort?

Answer 1

I find this in a Java document.

The sorting algorithm is a double rotary quick sorting by Vladimir Yaroslavsky, John Bentley and Joshua Bloch. This algorithm provides O (n log (n)) performance for many datasets, which lead to a deterioration in the quadratic performance of other quick sorts, and, as a rule, faster than traditional implementations (with one turn) of quick sort.

Then I find it in Google search results. Here is a quick sort algorithm:

1. Select an element called a summary from the array.
2. Reorder the array so that all elements smaller than the summary appear before the summary, and all elements larger than the summary follow it (equal values ​​can occur anyway). After this splitting, the rotation element is in its final position.
3. Recursively sort a nested array of smaller elements and a nested array of large elements.

For comparison: quick sort with two pivot points:

( )

1. For small arrays (length <17), use the insertion sorting algorithm.
2. Select the two pivots P1 and P2. For example, we can get the first element a [left] as P1 and the last element a [right] as P2.
3. P1 must be less than P2, otherwise they will change places. So, there are the following parts:
   • part I with indices on the left + 1 to L - 1 with elements that are less than P1,
   • Part II with indices from L to K - 1 with elements that are greater than or equal to P1 and less than or equal to P2,
   • part III with indices from G + 1 to the right - 1 with elements greater than P2,
   • Part IV contains the remaining elements that need to be investigated with indices from K to G.
4. The next element a [K] from part IV is compared with the two axes P1 and P2 and placed in the corresponding part I, II or III.
5. Pointers L, K and G change in the corresponding directions.
6. Steps 4 - 5 are repeated until K ≤ G.
7. The rotary element P1 is replaced by the last element from part I, the rotary element P2 is replaced by the first element from part III.
8. Steps 1 through 7 are repeated recursively for each part I, part II, and part III.

Answer 2

For those interested, see 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 indicated in the source:

"Sorts the given array range using the given array of the workspace array, if possible, to merge

The algorithm provides O (n log (n)) performance in many datasets, which lead to performance degradation in fast segments to quadratic performance and usually faster than traditional (single-threaded) Quicksort implementations.

Answer 3

I just want to add that from the point of view of the algorithm (i.e., the cost takes into account only the number of comparisons and permutations), 2-pivot quicksort and 3-pivot quicksort are no better than the classic quicksort (which uses 1 pivot), if not worse. However, in practice they work faster because they take advantage of modern computer architecture. In particular, their number of caches is less. Therefore, if we delete all the caches and we only have the processor and main memory, in my understanding, 2/3 pivot quicksort is worse than classical quicksort.

Links: 3-pivot Quicksort: https://epubs.siam.org/doi/pdf/10.1137/1.9781611973198.6 Analysis of why they work better than the classic Quicksort: https://arxiv.org/pdf/1412.0193v1.pdf Full and not too detailed information: https://algs4.cs.princeton.edu/lectures/23Quicksort.pdf