StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy is QuickSort Single pivot faster than 3-way partition?
text
Body
copied!<p>I am trying to roughly benchmark the performance of QuickSorts (Single Pivot, 3-way and Dual Pivot). </p> <p><strong>Questions 1 :</strong> I am afraid that I am missing something in the implementation of 3-way partition. Across several runs against random inputs (of 10 million) numbers, I could see that the single pivot always performs better (although the difference is somewhere around 100 milliseconds for 10 million numbers). </p> <p>I understand that the whole purpose of 3-way is not 0 (n^2) performance on duplicate keys - which is very evident when I run it against duplicate input. But is it true that for the sake of handling duplicate data, a small penalty is taken by 3-way? Or my implementation is bad?</p> <p><em><strong>Duplicate Data :</em></strong> </p> <ul> <li>Quick Sort Basic : 888 millis</li> <li>Quick Sort 3 Way : 522 millis</li> <li>Quick Sort Dual Pivot : 482 millis</li> </ul> <p><em><strong>Random Data :</em></strong></p> <ul> <li>Quick Sort Basic : 1677 millis</li> <li>Quick Sort 3 Way : 1717 millis</li> <li>Quick Sort Dual Pivot : 1595 millis</li> </ul> <p><strong>Question 2 :</strong> </p> <p>The Dual Pivot implementation (link below) does not handle duplicates well. It takes a 0(n^2) time to execute. Is there a good way to fast-forward. I could see that we could check if the pivots are equal and increment pivot1 until it is different than pivot2. Is this a fair implementation?</p> <pre><code>else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } </code></pre> <p><strong>Implementation links :</strong></p> <p>Root folder : <a href="https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick" rel="nofollow">https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick</a></p> <p>QuickSort (Single Pivot) : <a href="https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java" rel="nofollow">https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java</a></p> <p>QuickSort (3-way partition) : <a href="https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java" rel="nofollow">https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java</a></p> <p>QuickSort (Dual Pivot) : <a href="https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java" rel="nofollow">https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java</a></p> <p>TestCase : <a href="https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java" rel="nofollow">https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java</a></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload