Kiirsortimine

Allikas: Vikipeedia
Jump to navigation Jump to search
Kiirsortimine
Sorting quicksort anim.gif
Kiirsortimise visualisatsioon
Algoritmi liik Sortimisalgoritm
Ajaline keerukus halvimal juhul
Ajaline keerukus keskmiselt
Ajaline keerukus parimal juhul
Mahuline keerukus

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]

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 | muuda lähteteksti]

  1. "Sir Antony Hoare". Computer History Museum. Originaali arhiivikoopia seisuga 2015-04-03. Vaadatud 2015-04-22. 
  2. Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM 4 (7): 321. doi:10.1145/366622.366644. 
  3. Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN 978-1-84800-069-8.