bild
Skolan för
elektroteknik
och datavetenskap

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, resten i den andra. 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.
 * 
 * Precondition: first < last.
 */
(int low, int high) 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
        //
        //       < pivot   = pivot      unknown     > pivot
        //     -----------------------------------------------
        // v: |          |          |a            |           |
        //     -----------------------------------------------
        //     ^          ^          ^           ^           ^
        //    first      low        mid         high        last
        //
        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.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2012-03-04