Ātrās kārtošanas algoritms
Ātrās kārtošanas algoritms ir kārtošanas algoritms, kuru izstrādāja Sers Čārlzs Antonijs Ričards Hoars (C.A.R. Hoare) Britu datorzinātnieks 1960. gadā kad bija 26 gadus vecs, un tas ir viens no plašāk izmantotajiem kārtošanas algoritmiem. Šī algoritma vidējā sarežģītība ir O ( n log ⁡ n ) {\displaystyle {O}(n\log n)} . Sliktākajā gadījumā algoritma sarežģītība ir O ( n 2 ) {\displaystyle {O}(n^{2})} tomēr, ja algoritmu lieto pareizi, tad šāds gadījums ir novērojams reti. Parasti ātrās kārtošanas algoritms ir ātrāks kā citi O ( n log ⁡ n ) {\displaystyle {O}(n\log n)} sarežģītības kārtošanas algoritmi, galvenokārt tādēļ, ka algoritma iekšējais cikls ir viegli uzlabojams un piemērojams nepieciešamajam gadījumam. Ātrās kārtošanas algoritma labās īpašības ir kārtošana bez papildu atmiņas (tiek izmantots neliels steks), mazais salīdzināšanu skaits, kā arī algoritma īsais iekšējais cikls.