Quicksort
Väljer ett värde, pivotelementet, och flyttar mindre värden till vänster om det och större till höger. Sedan gör den samma sak med varje sida.
- bästa fall Ω(n log n)
- genomsnitt Θ(n log n)
- värsta fall O(n²)
- minne O(log n)
- inte stabil
- utan extra minne
Vad betyder det här?
- Bästa fall: hur tiden växer med listans storlek n när indata är den lättaste för den här algoritmen.
- Genomsnitt: hur tiden brukar växa med n. Med n² tar dubbla antalet värden ungefär fyra gånger så lång tid. n log n växer mycket långsammare.
- Värsta fall: tillväxten på den svåraste indatan. Viktigt när hastigheten aldrig får sjunka.
- Minne: hur mycket extra minne som behövs utöver listan. 1 betyder några variabler, n betyder en kopia av listan.
- Stabil: två lika värden behåller sin ursprungliga ordning. Viktigt när man sorterar poster efter ett fält.
- Utan extra minne: sorterar inuti själva listan, utan en andra lista.
- jämförs
- flyttas
- pivotelement
- på slutgiltig plats
Tryck på Spela upp: linjerna visar hur kostnaden växer
Tryck på Spela upp eller gå igenom algoritmen steg för steg.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
Prova det här: Välj en omvänd lista. Pivotelementet är alltid det minsta eller största kvarvarande värdet, så ena sidan blir tom och kostnaden går mot n².
Så fungerar det
Här är pivotelementet det sista värdet i intervallet. Från vänster till höger byts varje värde som inte är större än pivotelementet över till vänster sida. Sedan hamnar pivotelementet mellan de två sidorna, där det stannar för gott. Varje sida sorteras sedan på samma sätt.
När det är ett bra val
Ett av de snabbaste sätten att sortera i praktiken, och den behöver nästan inget extra minne. Men om den hela tiden väljer ett dåligt pivotelement, till exempel på en redan sorterad lista, blir den långsam. Riktiga versioner väljer pivotelementet noggrannare.