Quicksort
Quicksort är en rekursiv, i normalfallet, mycket snabb sorteringsalgoritm.
sortering med quicksort
Som namnet utlovar så är quicksort mycket snabb sortering med tidkomplexitet i normalfallet på O(N * log N). Det gör den snabbare än sortering med insertsort O(N
2) eller bubblesort O(N
2). Worst-case har dock även quicksort en tidskomplexitet på O(N
2), men då ska man ha otur.
Algoritm
Quicksort bygger på att vi först grovt sorterar tal under ett visst värde (vi kallar det pivot -tal) i en hög, över värdet i en annan hög. Ungefär som en mycket grov städning där hemma, där man först gör några få stora högar. Därefter fokuserar vi på de grova högarna och delar upp dem i bättre sorterade högar. I slutändan har alla högar försvunnit och vi har lyckats sortera allt perfekt.
pivot
Vi börjar med att välja ett pivot-tal, helst något i mitten av listan. Exakt hur man maskinellt kan välja ett pivot-tal tar vi längre fram. Men för att illustrera en grej här, låt oss bara välja ett pivottal, t.ex. 564.
Häng med nu.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
580 |
565 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
1 |
4 |
Vi skall nu möblera om i denna lista så att talen till vänster är mindre än pivot -talet och talen till höger är högre än pivot-talet.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
580 |
565 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
1 |
4 |
Vi går nu från vänster och letar efter tal på vänster sida som är större än pivot -talet. Dessa skall flyttas till högersida. Vi går också från höger på höger sida och tittar efter tal som är lägre än pivot -talet, dessa skall flyttas till vänster sida.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
580 |
565 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
1 |
4 |
Vi ser direkt att 580 är högre än pivot och skall flyttas till höger. Vi ser att 4 är lägre än pivot och skall flyttas till vänster sida.
Så vi byter plats på dessa!
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
565 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
1 |
580 |
Vi går sedan vidare till nästa tal på vänster sida som är högre än pivot och gör samma sak på höger sida, för att se vilket som är mindre än pivot och skall till vänster sida.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
565 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
1 |
580 |
Vi hittar även denna gång 2 tal som kan byta plats med varandra.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
565 |
580 |
Vi fortsätter ...
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
564 |
43 |
4 |
1233 |
12 |
3 |
565 |
580 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
3 |
43 |
4 |
1233 |
12 |
564 |
565 |
580 |
Vi fortsätter, denna gång kommer vänstersidan traversera fram ett antal steg innan den hittar ett värde större än pivot -talet.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
3 |
43 |
4 |
1233 |
12 |
564 |
565 |
580 |
Vi byter plats på dessa...
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
3 |
43 |
4 |
12 |
1233 |
564 |
565 |
580 |
När detta är gjort kommer i och j krocka med varandra och
partition returnerar med värdet 6 (dvs j-värdet). Begrunda position nummer 6 här nedan.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
4 |
1 |
5 |
3 |
43 |
4 |
12 |
1233 |
564 |
565 |
580 |
Talen till vänster om markerade området, de befinner sig i rätt område även om de inbördes är lite o-ordning. Samma med det markerade området. De hör också hemma på dessa positioner även om det är inbördes o-ordning.
Det som händer härefter, det är att quicksort kommer rekursivt anropa sig själv 2 gånger, dels för att sortera position 0-6 för och dels för att sortera 7-10 för sig. Det kommer bli allt mindre listor att få ordning på.
Dvs exakt samma sak som vi gått igenom, händer igen, fast med lite mindre data (kortare listor). När inget återstår sortera är algoritmen klar. För att slippa klippa och klistra i listan, så kan vi låta
partition arbeta mellan två värden, 2 pekare, på listan, lo och hi.
Hur väljer man pivot-tal ?
Idealfallet är ett pivot-tal i mitten av listan. Det är dock inte fullt så enkelt eftersom entropin ("oordningen") i listan eventuellt inte är perfekt. Eftersom vi kan anta att listan är någorlunda slumpartat (da!, det är väl därför vi sorterar den?) så kan vi egentligen ta vilket tal som helst, t.ex. första talet. I nedan implementation använder vi första talet. En annan variant är att t.ex. ta första, sista och mellersta värdet och ta medianen på dessa 3 värden. Ett bra pivot -tal sparar tid, men ett bra pivot -tal tar också tid att räkna fram. Man vill inte gärna lägga ner mer tid på att hitta ett bra pivot -tal än vad man vinner på det. Det är ofta inte superkritiskt med optimalt pivot -tal.
lista = [580,565,5,564,43,4,1233,12,3,1,4]
def quicksort(lst, lo, hi):
if lo >= 0 and lo < hi and hi >=0:
p = partition(lst, lo, hi)
quicksort(lst, lo, p)
quicksort(lst, p + 1, hi)
def partition(lst, lo, hi):
pivot = lst[lo]
i = lo
j = hi
while True:
while(i < hi and lst[i] < pivot):
i = i + 1
while(j > lo and lst[j] > pivot):
j = j - 1
if(i>=j):
return(j)
(lst[i],lst[j])=(lst[j],lst[i])
i = i + 1
j = j - 1
print(lista)
quicksort(lista,0,len(lista)-1)
print(lista)
lista = [580,565,5,564,43,4,1233,12,3,1,4]
def quicksort(lst, lo, hi):
if lo >= 0 and lo < hi and hi >=0:
p = partition(lst, lo, hi)
quicksort(lst, lo, p)
quicksort(lst, p + 1, hi)
def partition(lst, lo, hi):
pivot = lst[lo]
i = lo
j = hi
while True:
while(i < hi and lst[i] < pivot):
i = i + 1
while(j > lo and lst[j] > pivot):
j = j - 1
if(i>=j):
return(j)
(lst[i],lst[j])=(lst[j],lst[i])
i = i + 1
j = j - 1
print(lista)
quicksort(lista,0,len(lista)-1)
print(lista)
Notiser
Ovan algoritm är en av oss pythonifierad algoritm av
Tony Hoare, den som beskriver 2 pekare i en partition ovan. Det finns många varianter på temat. Denna artikel byggs ut vid behov men ovan beskriver konceptet ganska bra.