Quicksort

Quicksort

Sorteringsalgoritm som i genomsnittsfallet är optimal. Baserad på söndra-och-härska (dela och byt plats).

Animation som visar Quicksort-algoritmen över ett antal osorterade staplar. De röda staplarna markerar pivot-element; vid animationens början väljs elementet längst till höger som pivot.

Parvis jämförelse, söndra-och-härska-algoritm, sorteringsalgoritm

Under­klass till	• algoritm  • kombinatorisk algoritm   • sorteringsalgoritm
Upp­täc­ka­re eller upp­fin­na­re	Charles Antony Richard Hoare
Upp­täckts­da­tum	1961
Tids­komp­lex­i­tet i värsta fall	$O(n^{2})$
Tids­komp­lex­i­tet i bästa fall	$O(n\log n)$
Tids­komp­lex­i­tet i medel	$O(n\log n)$
Rums­komp­lex­i­tet i värsta fall	$O(n^{2})$
Rums­komp­lex­i­tet i medel	$O(\log n)$

Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara Tony Hoare^(en). Den sorterar $n$ objekt med tidskomplexitet $O(n^{2})$ i värsta fall och med en genomsnittlig tidskomplexitet $O(n\log n)$.

Algoritmen

Quicksortalgoritmen är av typen söndra och härska, och består av följande steg:

1. Välj ett element, kallat pivot-element, ur listan.
2. Ordna om listan så att alla element som är mindre eller lika med pivot-elementet kommer före detta, och så att alla element som är större än pivot-elementet kommer efter detta. Pivot-elementet har nu fått sin rätta plats.
3. Sortera rekursivt de två dellistorna, det vill säga med just denna algoritm.

Basfallet för rekursionen är en lista med ett element (i vissa implementationer används en tom lista som basfall).

Val av pivot-element

I tidiga versioner av Quicksort valdes ofta det första elementet i listan som pivot-element. Detta orsakar olyckligtvis sämsta möjliga beteende för redan sorterade listor, vilket är ett relativt vanligt användningsfall. Problemet löstes enkelt genom att välja ett pivot-element slumpmässigt, välja ett element i mitten av listan eller (särskilt för längre listor) välja medianen av det första, mittersta och sista elementet (vilket rekommenderas av Robert Sedgewick). Den senare regeln - "medianen-av-tre" - motverkar fallet med sorterad (eller omvänt sorterad) indata och ger ett bättre estimat för det optimala pivot-elementet (den egentliga medianen) än vad som fås genom att godtyckligt välja ett enskilt element, när ingen annan information om ordningen på indatat är känd.

Exempel

Haskellkod

Exempelkod i Haskell:

  sort []           = []
  sort (pivot:rest) = 
                      sort [y | y <- rest, y < pivot] 
                      ++ [pivot] ++ 
                      sort [y | y <- rest, y >=pivot]

Översiktligt: "små element" + pivot + "stora element". Notera att det första elementet i listan väljs som pivotelement vilket kan leda till dåliga prestanda om listan från början är (nästan) sorterad eller inverterat sorterad.

C-kod

Två funktioner "swapItems" och "compare" antas finnas tillgängliga för ett indexerbart objekt för att kasta om respektive göra jämförelser mellan objektets element.

quickSort(int          size,
          swapFuncType swapItems,
          compFuncType compare)
{
	partitioning(0, size - 1, swapItems, compare);
}

partitioning(int          low,
           int          high,
           swapFuncType swapItems,
           compFuncType compare)
{
    if (low >= high) {
        return; 
    }
    if (high - low == 1) {
        if (compare(low, high)) {
            swapItems(low, high);
        }
        return;
    } 
    int partition = high;
    int i, j;
    do {
        // Flytta indexen i riktning mot pivotelementet:
        i = low;
        j = high;
        while ((i < j) && !compare(i, partition)) {
            i++;
        }
        while ((j > i) && (compare(j, partition))) {
            j--;
        }            
        if (i < j) {
            swapItems(i, j);
        }
    } while (i < j);
    // Flytta pivotelementet till dess rätta plats i listan:             
    swapItems(i, high); 
    // Anropa partioneringsproceduren rekursivt 
    if ((i - low) < (high - i)) {
		partitioning(low,  i - 1, swapItems, compare);
		partitioning(i + 1, high, swapItems, compare);
    } 
    else {
		partitioning(i + 1, high, swapItems, compare);
		partitioning(low, i - 1, swapItems, compare);
    }
}