-
Notifications
You must be signed in to change notification settings - Fork 48
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Quicksort 'Magnetica' submission #73
Comments
I may have found a way to successfully port it into our program. I do need to know, though, does this visual seem correct? |
Congratulations, you appear to have reinvented ternary quicksort with Yaroslavskiy partitioning and "middle element" pivot selection. Given that, the visualisation looks correct to me. |
@PCBoyGames @chromi Does he have single-pivot variant along with dual-pivot one? My Magnetica uses single-pivot. |
Both ternary and dual-pivot quicksort create three partitions, just on slightly different criteria. Your method of doing so is the same, and characteristically leaves the equal-to-pivot values in the middle so they don't have to be swapped into position again. I have a version of quicksort that selects two pivots (using a random sampling method, which avoids quadratic pathologies much better than any fixed choice), then checks whether they are equal to each other. If they are, it does a ternary partition very like yours. If not, it does a dual-pivot partition very like Yaroslavskiy's. This tends to obtain the best qualities of both. |
It seems you have superior strategy, bravo. |
You could choose pivots deterministically as well, for example by taking the 0/7, 1/7, …, 7/7 positioned elements, sorting them (insertion sort is good enough), then choosing the 3rd and 6th ranked as two pivots (ie. tertiles of 8). Or the 0/4, ¼, ½, ¾, 4/4 positioned, then the 3rd ranked for a single pivot (ie. median of 5). It is still possible to deliberately create inputs that provoke quadratic behaviour with this (eg. ArrayV has an "AntiQSort" mode that generates them), but you should find fewer cases where your pivot is wildly out of place on average. Or, for benchmarking, you could seed the RNG with a consistent value, but switch to a truly random seed in production. Then instead of picking samples from fixed positions, you use the RNG to choose them, then proceed as above. Finally, you will want to switch from quicksort to a simpler algorithm for small partitions, for which the work of selecting a good pivot and setting up the partitioning algorithm becomes a large overhead. Insertion sort becomes superior below about a dozen elements. Shellsort with a good choice of gap sequence could be a win for as much as 4000 elements:
The above uses a modified Sedgewick 1982 sequence: 1073, 281, 77, 23, 8, 3, 1. |
@chromi
Just found this gold benchmark/source mine: Love the branchless etudes, so my intent is to choose Pivot as the middle of 6 or 7 elements ... chosen somehow. LOVE the whole experimental attitude from all the coders there. What is your favorite among these golden etudes? |
Recommendation: Join our Discord, The Studio |
In case you want to use the best I could write so far: It chooses median of 5 pivot - branchlessly! Again, it outperforms both! But, now it is more robust against quadratic behavior - surely will scream with 'Organ Pipe' and such... On laptop with i5-7200U 3.1GHz max turbo, 36GB DDR4 2133MHz:
|
How does it compare against PDQSort? |
@Gaming32 |
I have sent the algorithm in as part of a pull request to the ArrayV Extra Sorts Pack. Keep an eye out: Gaming32/ArrayV-Extra-Sorts#1 |
Hi,
please add to your beautiful collection the fastest (known to me) Quicksort:
https://www.qb64.org/forum/index.php?topic=3518.msg138244#msg138244
The text was updated successfully, but these errors were encountered: