Quicksort
Quicksort er en af de mest brugte sorteringsalgoritmer. Den vælger en pivot, deler listen i værdierne, der er mindre end pivoten, og resten, og sorterer de to sider på samme måde. Den er hurtig i praksis og behøver ingen ekstra liste, men hvor hurtig afhænger af pivoten.
Idéen
Vælg én værdi som pivot. Omarrangér listen, så hver værdi, der er mindre end pivoten, kommer før den, og hver anden værdi efter den. Den omarrangering kaldes en partitionering, og den efterlader pivoten præcis hvor den hører til i den sorterede liste. De to sider er nu uafhængige problemer: sortér hver af dem med quicksort. En side med én værdi eller ingen er allerede sorteret.
Partitioneringen, trin for trin
Appen bruger Lomuto-partitionering. Pivoten flyttes til enden af delen. En markør starter i begyndelsen: alt før den er mindre end pivoten. Hver anden værdi sammenlignes med pivoten; er den mindre, byttes den til markøren, og markøren rykker én plads frem. Til sidst byttes pivoten til markøren. Tag 5, 1, 4, 2, 8 med den sidste værdi som pivot: alle fire værdier er mindre end 8, så 8 bliver i enden. Delen 5, 1, 4, 2 partitioneres omkring 2, hvilket giver 1, 2, 4, 5, og 4, 5 omkring 5. Det er 8 sammenligninger, 2 ombytninger og 3 partitioneringer.
Gode og dårlige pivoter
Hvis hver pivot landede i midten, ville hver partitionering halvere problemet, og sorteringen ville kræve cirka n log₂ n sammenligninger. På en tilfældig liste er pivoterne sjældent perfekte, men som regel gode nok: for 40 tilfældige værdier tæller appen cirka 190 sammenligninger. Det værste tilfælde opstår, når pivoten hver gang er den mindste eller største værdi. Med den sidste værdi som pivot gør en liste, der allerede er sorteret eller omvendt, præcis det: hver partitionering fjerner kun pivoten, og sorteringen kræver n(n − 1)/2 sammenligninger, 780 for 40 værdier.
Valg af pivot
En tilfældig pivot gør det værste tilfælde ekstremt usandsynligt for ethvert input, fordi ingen bestemt rækkefølge kan narre den. Median af tre, den midterste værdi af det første, midterste og sidste element, er billig og klarer sorterede og omvendte lister godt. Prøv begge på en sorteret liste i appen, og sammenligningerne falder fra 780 til cirka 150. Mange ens værdier er et andet problem: de havner alle på samme side af pivoten. En tredelt partitionering, der holder værdierne lig med pivoten i en midterdel, løser det.
Historie og brug
Tony Hoare opfandt quicksort i 1959 og offentliggjorde den i 1961. Hans egen partitionering scanner fra begge ender og laver færre ombytninger; den enklere Lomuto-version, der vises her, blev populær gennem lærebøger. Quicksort sorterer på stedet, og dens inderste løkke er meget kort, så den er som regel hurtigere end flettesortering i praksis, selvom den ikke er stabil. Introsort, sorteringen bag C++' standardbibliotek, kører quicksort og skifter til heapsort, hvis partitioneringerne bliver for skæve, så dens værste tilfælde forbliver n log n.
Udforsk den
Åbn appen, og tryk på Trin. Delen, der partitioneres, er skraveret, pivoten har sin egen farve, og den stiplede linje markerer enden af venstre del, værdierne, der er mindre end pivoten. Hver pivot bliver grøn, når den når sin endelige plads. Vælg en sorteret liste og den sidste værdi som pivot, skift så til median af tre, og sammenlign tællerne.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten af quicksort?
O(n log n) i gennemsnit og med gode pivoter, O(n²) i værste fald. Den sorterer på stedet; rekursionen bruger O(log n) ekstra hukommelse, når den mindste side sorteres først.
Hvad er forskellen på Lomuto- og Hoare-partitionering?
Lomuto holder én markør og scanner fra venstre mod højre, hvilket er let at følge og er det, denne app viser. Hoare scanner fra begge ender mod hinanden og bytter par, der står på den forkerte side, hvilket i gennemsnit giver cirka tre gange færre ombytninger.
Hvorfor er quicksort langsom, når mange værdier er ens?
Værdier lig med pivoten havner alle på samme side, så en liste med få forskellige værdier deles skævt, og en liste med ens værdier er lige så slem som det værste tilfælde. En tredelt partitionering, der samler værdierne lig med pivoten i midten, undgår det.
Er quicksort stabil?
Nej. Ombytninger under en partitionering flytter værdier over lange afstande, så ens værdier kan skifte rækkefølge.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv quicksort