Quicksort

Fra Wikipedia, den frie encyklopedi

Quicksort er en «splitt-og-hersk»-sorteringsalgoritme som benytter en partisjoneringsfunksjon.

For å partisjonere en liste velger vi et element som vi kaller pivot, og flytter alle elementer som er mindre enn pivot før, og alle som er større eller lik etter pivot. Deretter gjøres tilsvarende for hver av de to del-listene på hver side av pivot, helt til alle de minste del-listene av lengde én og to er sortert. Da er hele listen sortert. En kritisk del av algoritmen er å velge et fornuftig pivot-element; dårlige valg kan føre til svært dårlig ytelse, men dersom man velger medianen hver gang, vil algoritmen bruke O(n log n) tid.

Effektive implementasjoner av quicksort er typisk ganske kompliserte, men er samtidig blant de raskeste sorteringsalgoritmene i praksis. Sammen med beskjedent minnekrav gjør dette quicksort til en populær sorteringsalgoritme, brukt av mange standardbiblioteker.