Quicksort
We should forget about small efficiencies,
say about 97% of the time: premature optimization
is the root of all evil.
– Donald E. Knuth
Quicksort är en av de snabbaste sorteringsalgoritmerna.
Den bygger på en enkel idé men är ganska
komplicerad att implementera om man vill få bra
prestanda för alla typer av indata.
I quicksort väljer man först ut ett av elementen p,
det så kallade pivot-elementet, och delar sedan upp vektorn
i två delar, så att alla element som är mindre än eller lika
med p hamnar i den första delen.
Sedan återstår bara att sortera de två delvektorerna rekursivt.
// Sorts the elements of the subvector v[first..last].
void qsort(int[] v, int first, int last) {
if (first >= last) // Less than two elements
return;
// Choose a pivot element.
int p = v[first];
// Partition the elements so that every number of
// v[first..mid] <= p and every number of v[mid+1..last] > p.
int mid = partition(v, first, last, p);
qsort(v, first, mid);
qsort(v, mid+1, last);
}
Med lite tur så kommer den här algoritmen att kunna bli mycket snabb.
Om vi antar att partitioneringen kan göras på linjär tid (vilket lätt
kan uppnås) och att den alltid delar upp vektorn i två precis
lika stora delar (vilket är högst osannolikt)
så blir rekursionsekvationen för tiden T(n) att sortera
en vektor med n element
- T(n) = 1, när n ≤ 1,
- T(n) = n + 2T(n/2), när n > 1.
En räkning, eller mästarsatsen, visar att
T(n) = O(nlog(n)).
För att uppnå detta måste man dock välja pivot-elementet p
med större omsorg än i exemplet ovan.
Det kanske mest naturliga valet är att låta p vara medianen
av elementen i v[first..last].
Närmre mitten än så kan man ju inte komma.
Det går att beräkna medianen på linjär tid,
men algoritmerna är så komplicerade att
man tappar alltför mycket prestanda.
Men situationen är mer komplicerad än så.
Vi kan få problem även om vi delar upp elementen runt medianen.
Om samtliga tal i v[first..last] är lika så kommer
partitioneringen att helt misslyckas: alla element är ju då
lika med pivot-elementet.
Pivotelement
Att välja ett lämpligt pivot-element p
är en balansakt. Om vi lägger ned alltför lite arbete,
som i exemplet ovan där vi sätter p = v[first],
så riskerar vi att få en väldigt skev partitionering.
Om vi i stället lägger ner för mycket arbete, genom att till
exempel beräkna medianen, så kan partitioneringen bli bättre
men alltför långsam.
Den kanske enklaste lösningen är att låta pivot-elementet vara ett
slumpmässigt valt tal ur v[first..last]. Det förväntade
antalet jämförelser för att sortera en vektor där alla element
är olika blir då 1.39nlog(n).
Ett val av pivot-element som man ofta ser är
p = median(v[first], v[first + (last-first)/2], v[last]).
Man hoppas då att åtminstone ett av dessa tre tal ska ligga nära mitten
och argumenterar att detta kommer att gälla för alla "rimliga" former
av indata. Min erfarenhet är att detta inte alltid stämmer. Om man
väljer pivot-element på detta sätt och använder partitioneringsalgoritmen
i nästa avsnitt så får man till exempel väldigt dåliga resultat när indata
består av en redan sorterad vektor.
En mer robust lösning är att kombinera båda idéerna och välja
pivot-elementet som medianen av tre slumpmässigt valda element.
Partitionering
För att undvika att partitioneringen blir skev om man har
många dubbletter i vektorn så kan man i stället
dela upp talen i tre grupper:
de som är mindre än p,
de som är lika med p
och de som är större än p.
Om man placerar alla element som är lika med pivot-elementet i
mitten så behöver man bara sortera de andra två delarna.
Med hjälp av en lämpligt vald loop-invariant får vi
ordning på den ganska komplicerade koden.
/**
* Reorders the elements of the subarray v[first..last] so that
* all elements in v[first..low-1] are less than pivot,
* all elements in v[low..high] are equal to pivot,
* all elements in v[high+1..last] are greater than pivot.
* Returns (low, high).
* Precondition: first < last.
*/
(int, int) partition(int[] v, int first, int last, int pivot) {
int low = first;
int mid = first;
int high = last;
while (mid <= high) {
// Invariant:
// v[first..low-1] < pivot
// v[low..mid-1] = pivot
// v[mid..high] are unknown
// v[high+1..last] > pivot
int a = v[mid];
if (a < pivot) {
v[mid] = v[low];
v[low] = a;
low++;
mid++;
} else if (a == pivot) {
mid++;
} else { // a > pivot
v[mid] = v[high];
v[high] = a;
high--;
}
}
return (low, high);
}
Man ser lätt att tidskomplexitet är linjär: varje
varv i slingan tar konstant tid och avståndet mellan
mid och high krymper i varje varv,
antingen genom att mid blir större eller
att high blir mindre.
Det går att optimera partitioneringskoden ytterligare,
men då på bekostnad av läsbarhet och enkelhet.
Kombinationsalgoritmer
Erfarenheten visar att quicksort är den snabbaste
jämförelsebaserade sorteringsalgoritmen för
många typer av indata. Ibland finns det dock enklare
och snabbare alternativ. Insättningssortering, som
visserligen har kvadratisk värstafallstid, är
till exempel snabbare för små sorteringsproblem.
I stället för att välja antingen quicksort eller
insättningssortering så kan man med fördel kombinera
algoritmerna: använd quicksort för att sortera
delvektorer v[first..last] med många element
och insättningssortering om antalet element är litet.
Brytpunkten beror på många faktorer (hur koden är skriven,
hur indata ser ut, maskinens prestanda) och måste därför
provas ut experimentellt.
Lyckligtvis visar det sig ofta att valet inte
är så kritiskt; brytpunkter mellan 10 och 100
brukar fungera bra.