1
$\begingroup$

I've seen to explanations for the quick sort algorithm.

One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted.

Another involved a more complicated solution involving two pivots which interchanged.

What are the benefits of either solution, why was the dual-pivot solution created? Is it faster?

$\endgroup$
1
$\begingroup$

Basically Dual-pivot Quicksort buys you two items: The best case running time is $\Theta(n \log_3 n)$ instead of $\Theta(n \log_2 n)$ since each partition is the third part of the entire current range. Also, if one pivot is not good (it is close to one of the ends of the current range), there is a good chance that the second pivot will be better.

$\endgroup$
  • $\begingroup$ I looked further into it, and the dual pivot system seems to just be a (complicated-looking) way of partitioning the array with O(n) time-complexity. $\endgroup$ – Tobi Jun 18 '17 at 21:38
  • $\begingroup$ They weren't actually pivots, but pointers. Unless I'm mistaken and have come across a 3rd type of implementation/explanation $\endgroup$ – Tobi Jun 18 '17 at 21:43
  • 1
    $\begingroup$ $\Theta(n \log_3 n)$ is the same thing as $\Theta(n \log_2 n)$. $\endgroup$ – Gilles 'SO- stop being evil' Jun 18 '17 at 21:51
  • 1
    $\begingroup$ @Gilles Yes, but the point is that if the partitioning routine splits evenly, the recursion depth is smaller than in single-pivot quicksort. $\endgroup$ – coderodde Jun 18 '17 at 22:03
  • 1
    $\begingroup$ @Gilles Dual-pivot quicksort made it in JDK 7. I am rather confident that they actually benchmarked it against single-pivot version. $\endgroup$ – coderodde Jun 18 '17 at 22:17
0
$\begingroup$

This is a visualization of the algorithm. And this is claim

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.

$\endgroup$
  • $\begingroup$ From your link with the claim: "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.". Well, that's stupid because it means sorting a sorted array will take quadratic time. $\endgroup$ – gnasher729 Jun 19 '17 at 11:09
  • $\begingroup$ Sorted array is just one possibility out of thousands or millions possible permutations. In any case, it claims that "... O(n log(n)) performance on MANY DATA SETS that cause other quicksorts to degrade...". Theoretically, however you shuffle data, there is always a chance of ending up with sorted array unless you check the array is already sorted before you invoke quicksort. $\endgroup$ – fade2black Jun 19 '17 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.