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	• 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)$
Rums­komp­lex­i­tet i medel	$O(\log n)$

Quicksort (snabbsortering) ä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)$. Quicksortalgoritmen är av typen söndra och härska.

Algoritmen

Den grundläggande algoritmen handlar om att välja ut ett så kallat pivot-element och sortera listan så att alla mindre element hamnar till vänster om pivot-elementet och alla större element hamnar till höger om pivot-elementet. Pivot-elementet har då korrekt position i listan, vilket innebär att pivot-elementet är sorterat. Dock är vänstersidan med mindre element än pivot-elementet är fortfarande osorterad, liksom högersidan. Därför delas listan upp (partitioneras) i två delar: den vänstra sidan och den högra sidan. Då får man två dellistor som behöver sorteras. Dellistorna inkluderar alltså inte själva pivot-elementet eftersom det redan har sin rätta plats i listan. Dellistorna sorteras genom att Quicksort-algoritmen anropas rekursivt för båda delarna. Det innebär att dellistorna sorteras oberoende av varandra. I nästa anrop väljs alltså nya pivot-element för dellistorna som i sin tur bryts upp i ytterligare två dellistor var och så vidare

Mer formellt kan algoritmen beskrivas med nedanstående 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 prestanda för redan sorterade listor, vilket är ett relativt vanligt användningsfall. Samma ogynnsamma utfall fås om listan redan är sorterad och pivot-elementet väljs ut till det sista i listan.

En enkel lösning för att minska risken för ett ogynnsamt val av pivot-element är att välja ett pivot-element slumpmässigt eller välja ett element i mitten av listan.

En metod som mera robust undviker ogynnsamt val av pivot-element är att välja medianen av det första, mittersta och sista elementet, vilket rekommenderas av professor Robert Sedgewick. Den metod - "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, om ingen annan information om ordningen på indatat är känd.

En helt annan metod för att undvika ett ogynnsamt val av pivot-element är att slumpmässigt blanda (shuffla) listan innan den sorteras. Då blir det vanligtvis extremt osannolikt att listan ska hamna i helt sorterad ordning. Den metoden använder Robery Sedgewick i några av sina exempelalgoritmer.

Nackdelar

Det finns några nackdelar med Quicksort-algoritmen.

• En av nackdelarna är att algoritmen har tidskomplexitet $O(n^{2})$ i värsta fall. Det bör dock sägas att denna nackdel är mer teoretisk eftersom sannolikheten att en slumpmässigt blandad lista med många element hamnar i exakt storleksordning är praktiskt taget noll. (Detta förutsätter alltså att listan blandas [eng. sufflas] initialt innan själva Quicksort algoritmen körs). Om indata N är mindre ökar sannolikheten för att indata är sorterad även efter att listan har slumpmässigt blandats (shufflad). Men om N är litet så spelar det ingen praktisk roll att tidskomplexiteten blir kvadratisk eftersom algoritmen ändå går snabbt. Därför är Quicksort trots värsta fallet tiden på kvadratiskt n en effektiv algoritm i praktiken.
• Vidare är en annan nackdel (som inte endast är teoretisk) att Quicksort är en instabil sorteringsalgoritm. Det betyder att samma element i indata kan få olika inbördes ordning i utdata. Detta jämfört med Merge sort, vilket är en stabil algoritm. Stabiliteten får betydelse om exempelvis person-objekt ska sorteras. Listan kanske redan är sorterad med personnummer i första hand och namn i andra hand. Om Mergesort används kommer den inbördes ordningen att vara intakt, dvs. alla objekt som sorteras in under i första hand ett visst årtal förblir i andra hand sorterade i namnordning. Men detta garanteras ej av Quicksort.
• Vidare är en tredje nackdel med algoritmen att den presterar mindre bra för små indata. Denna nackdel kan dock kringgås genom att kombinera Quicksort med andra algoritmer, exempelvis Insättningssortering för de allra minsta indata. Oftast sker då brytningen när N når en storlek på mellan fem och 15.

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);
    }
}