Quicksort
Sorteringsalgoritm som i genomsnittsfallet är optimal. Baserad på söndra-och-härska (dela och byt plats). / From Wikipedia, the free encyclopedia
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.
Snabbfakta Underklass till, Upptäckare eller uppfinnare ...
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.
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 |
Stäng