Kiirsortimine
Kiirsortimine (ka kiirmeetod, Hoare'i meetod) on tõhus jaga-ja-valitse põhimõttel sortimisalgoritm. Selle töötas välja Tony Hoare 1959. aastal [1] ja avaldas 1961. a.[2] Algoritm on ka tänapäeval laialdaselt kasutuses. Hästi teostatuna on see umbes kaks kuni kolm korda kiirem oma peamistest alternatiividest, mestimissortimisest ja kuhjasortimisest.[3]
 Kiirsortimise visualisatsioon | |
| Algoritmi liik | Sortimisalgoritm |
|---|---|
| Ajaline keerukus halvimal juhul | |
| Ajaline keerukus keskmiselt | |
| Ajaline keerukus parimal juhul | |
| Mahuline keerukus | |
Kiirsortimine on võrdlussortimise algoritm, millega on võimalik sortida mis tahes elemente, millel on defineeritud "vähem kui" seos (formaalselt täielik järjestus). Efektiivses teostuses ei ole tegu stabiilse sortimisalgoritmiga, mis tähendab, et võrdsete elementide omavaheline järjestus võib muutuda. Kiirsortimine saab toimuda kohapeal (ilma massiivi kopeerimata) ja selle mäluvajadus on väike.
Viited muuda
- ↑ "Sir Antony Hoare". Computer History Museum. Originaali arhiivikoopia seisuga 3.04.2015. Vaadatud 22.04.2015.
- ↑ Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM. 4 (7): 321. DOI:10.1145/366622.366644.
- ↑ Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. Lk 129. ISBN 978-1-84800-069-8.