Dual-pivot snabbsort avser varianter av klassisk snabbsort där i partitionering steg två pivot används för att dela in i tre segment. Detta kan göras på olika sätt, vilket ger upphov till olika algoritmer. Nyligen fick en dual-pivot algoritm på grund av Yaroslavskiy mycket uppmärksamhet, eftersom den ersatte den välkonstruerade snabbväxande algoritmen i Oracles Java 7 runtime bibliotek. Nebel och Wild (ESA 2012) analyserade denna algoritm och visade att den i genomsnitt använder 1,9n ln n + O(n) jämförelser för att sortera en inmatning av storlek n, slå standard snabbsort, som använder 2n ln n + O(n) jämförelser. Vi introducerar en modell som fångar alla dual-pivot algoritmer, ger en enhetlig analys, och identifiera nya dual-pivot algoritmer som minimerar det genomsnittliga antalet nyckeljämförelser bland alla möjliga algoritmer upp till en linjär term. Detta minimum är 1,8 n ln n + O(n). För det fall att pivoterna väljs från ett litet prov, inkluderar vi en jämförelse av dual-pivot snabbsort och klassisk snabbsort. Speciellt visar vi att dual-pivot snabbsort drar nytta av en skev val av pivoter. Vi utvärderar våra algoritmer experimentellt och jämför dem med Yaroslavskiys algoritm och den nyligen beskrivna 3-pivot-quicksort-algoritmen Kushagra et al. Europaparlamentets och rådets förordning (EU, Euratom) nr 966/2012 av den 25 oktober 2012 om finansiella regler för unionens allmänna budget och om upphävande av rådets förordning (EG, Euratom) nr 1605/2002 (EUT L 298, 26.10.2012, s. 1).
Dessutom föreslog REF en 2-pivot algoritm som gör 2n ln n + O(n) jämförelser och 0,6n ln n + O(n) swappar i genomsnitt ingen förbättring jämfört med klassisk snabbsort i båda kostnadsåtgärder-, men beter sig mycket bra i praktiken.
Optimal Partitioning for Dual-Pivot Quicksort
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}