Quicksort

Från Wikipedia
Hoppa till: navigering, sök
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.

Quicksort är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Den sorterar n objekt med tidskomplexitet O (n2) i värsta fall och med en genomsnittlig tidskomplexitet O (n log n). En förutsättning för att man når denna komplexitet är att man väljer rätt pivot-element, ett slumpvist valt är bra men man brukar nöja sig med medianen av tre (ett från början ett från slutet och ett från mitten av listan).

Algoritmen[redigera | redigera wikitext]

Quicksortalgoritmen är av typen söndra och härska, och har stegen

  1. Välj ett element, kallat pivotelement, ur listan
  2. Ordna om listan så att alla element som är mindre eller lika med pivotelementet kommer före detta, och så att alla element som är större än pivotelementet kommer efter detta. Pivotelementet 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).

Exempel[redigera | redigera wikitext]

Haskellkod[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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)
{
	partioning(0, size - 1, swapItems, compare);
}

partioning(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)) {
		partioning(low,  i - 1, swapItems, compare);
		partioning(i + 1, high, swapItems, compare);
    } 
    else {
		partioning(i + 1, high, swapItems, compare);
		partioning(low, i - 1, swapItems, compare);
    }
}