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	Tony Hoare
Tidpunkt för upptäckt eller upp­fin­nan­de	1961
Tids­komp­lex­i­tet i värsta fall	${\displaystyle O(n^{2})}$
Tids­komp­lex­i­tet i bästa fall	${\displaystyle O(n\log n)}$
Tids­komp­lex­i­tet i medel	${\displaystyle O(n\log n)}$
Rums­komp­lex­i­tet i värsta fall	${\displaystyle O(n)}$
Rums­komp­lex­i­tet i medel	${\displaystyle 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 ${\displaystyle n}$ objekt med tidskomplexitet ${\displaystyle O(n^{2})}$ i värsta fall och med en genomsnittlig tidskomplexitet ${\displaystyle 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).

Nackdelar

Det finns några nackdelar med Quicksort-algoritmen.

• En av nackdelarna är att algoritmen har tidskomplexitet ${\displaystyle 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

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

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

Källor