Loading AI tools
Sorteringsalgoritm som i genomsnittsfallet är optimal. Baserad på söndra-och-härska (dela och byt plats). Från Wikipedia, den fria encyklopedin
Quicksort (snabbsortering) är en sorteringsalgoritm som används för att sortera objekt efter ett visst mått. Upphovsman anses vara Tony Hoare(en).[1] Den sorterar objekt med tidskomplexitet i värsta fall och med en genomsnittlig tidskomplexitet . Quicksortalgoritmen är av typen söndra och härska.
Underklass till | • kombinatorisk algoritm • sorteringsalgoritm | |
---|---|---|
Upptäckare eller uppfinnare | Charles Antony Richard Hoare | |
Upptäcktsdatum | 1961 | |
Tidskomplexitet i värsta fall | ||
Tidskomplexitet i bästa fall | ||
Tidskomplexitet i medel | ||
Rumskomplexitet i värsta fall | ||
Rumskomplexitet i medel |
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 [2]
Mer formellt kan algoritmen beskrivas med nedanstående steg:
Basfallet för rekursionen är en lista med ett element (i vissa implementationer används en tom lista som basfall).
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.[3] 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.[4]
Det finns några nackdelar med Quicksort-algoritmen.
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.
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);
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.