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). ![Redigera Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
![Redigera Wikidata](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
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. ![Redigera Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
![Redigera Wikidata](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Arbcom_ru_editing.svg/8px-Arbcom_ru_editing.svg.png)
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