Mine sisu juurde

Kiirsortimine

Allikas: Vikipeedia
Kiirsortimine
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.

  1. "Sir Antony Hoare". Computer History Museum. Originaali arhiivikoopia seisuga 3.04.2015. Vaadatud 22.04.2015.
  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. Lk 129. ISBN 978-1-84800-069-8.