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. 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
        //
        //       < 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 2011-01-16