Quicksort
Quicksort är en av de mest använda sorteringsalgoritmerna. Den väljer en pivot, delar listan i värdena som är mindre än pivoten och resten, och sorterar de två sidorna på samma sätt. Den är snabb i praktiken och behöver ingen extra lista, men hur snabb beror på pivoten.
Idén
Välj ett värde som pivot. Ordna om listan så att varje värde som är mindre än pivoten kommer före den och varje annat värde efter den. Den omordningen kallas en partitionering, och den lämnar pivoten exakt där den hör hemma i den sorterade listan. De två sidorna är nu oberoende problem: sortera var och en med quicksort. En sida med ett värde eller inget är redan sorterad.
Partitioneringen, steg för steg
Appen använder Lomuto-partitionering. Pivoten flyttas till slutet av delen. En markör börjar i början: allt före den är mindre än pivoten. Varje annat värde jämförs med pivoten; om det är mindre byts det till markören och markören flyttar fram ett steg. Till sist byts pivoten till markören. Ta 5, 1, 4, 2, 8 med sista värdet som pivot: alla fyra värden är mindre än 8, så 8 stannar i slutet. Delen 5, 1, 4, 2 partitioneras kring 2, vilket ger 1, 2, 4, 5, och 4, 5 kring 5. Det blir 8 jämförelser, 2 byten och 3 partitioneringar.
Bra och dåliga pivoter
Om varje pivot hamnade i mitten skulle varje partitionering halvera problemet, och sorteringen skulle kräva ungefär n log₂ n jämförelser. På en slumpad lista är pivoterna sällan perfekta men oftast tillräckligt bra: för 40 slumpade värden räknar appen ungefär 190 jämförelser. Värsta fallet uppstår när pivoten alltid är det minsta eller största värdet. Med sista värdet som pivot gör en lista som redan är sorterad, eller omvänd, precis det: varje partitionering tar bara bort pivoten, och sorteringen kräver n(n − 1)/2 jämförelser, 780 för 40 värden.
Att välja pivot
En slumpad pivot gör värsta fallet extremt osannolikt för alla indata, eftersom ingen särskild ordning kan lura den. Median av tre, mittvärdet av första, mittersta och sista elementet, är billig och klarar sorterade och omvända listor bra. Prova båda på en sorterad lista i appen så sjunker jämförelserna från 780 till ungefär 150. Många lika värden är ett annat problem: de hamnar alla på samma sida om pivoten. En trevägspartitionering, som håller värdena lika med pivoten i en mittdel, löser det.
Historia och användning
Tony Hoare uppfann quicksort 1959 och publicerade den 1961. Hans egen partitionering söker från båda ändar och gör färre byten; den enklare Lomuto-varianten som visas här blev populär genom läroböcker. Quicksort sorterar på plats och dess inre loop är mycket kort, så den är oftast snabbare än mergesort i praktiken, även om den inte är stabil. Introsort, sorteringen bakom C++:s standardbibliotek, kör quicksort och byter till heapsort om partitioneringarna blir för ojämna, så att värsta fallet förblir n log n.
Utforska den
Öppna appen och tryck på Steg. Delen som partitioneras är skuggad, pivoten har en egen färg, och den streckade linjen markerar slutet av vänsterdelen, värdena som är mindre än pivoten. Varje pivot blir grön när den når sin slutliga plats. Välj en sorterad lista och sista värdet som pivot, byt sedan till median av tre, och jämför räknarna.
Ofta ställda frågor
Vad är tidskomplexiteten för quicksort?
O(n log n) i genomsnitt och med bra pivoter, O(n²) i värsta fall. Den sorterar på plats; rekursionen behöver O(log n) extra minne när den mindre sidan sorteras först.
Vad är skillnaden mellan Lomuto- och Hoare-partitionering?
Lomuto har en markör och söker från vänster till höger, vilket är lätt att följa och är det som den här appen visar. Hoare söker från båda ändar mot varandra och byter par som står på fel sida, vilket i genomsnitt ger ungefär tre gånger färre byten.
Varför är quicksort långsam när många värden är lika?
Värden lika med pivoten hamnar alla på samma sida, så en lista med få olika värden delas ojämnt, och en lista med lika värden är lika illa som värsta fallet. En trevägspartitionering som samlar värdena lika med pivoten i mitten undviker det.
Är quicksort stabil?
Nej. Byten under en partitionering flyttar värden över långa avstånd, så lika värden kan byta ordning.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova quicksort