Ā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 . Sliktākajā gadījumā algoritma sarežģītība ir  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  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.

Vēsture

Ātrās kārtošanas algoritmu 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. Tas tika izstrādāts, laikā kad tā autors atradās Padomju Savienībā Maskavas Universitātē kā apmaiņas students, algoritma mērķis bija sakārtot tulkot nepieciešamos vārdus tā, lai tie būtu vienkāršāk saistīti savā starpā.

Sarežģītā versija

Vienkāršās versijas mīnuss ir tāds, ka to izmantojot nepieciešama O(n) papildus atmiņa, kas ir tikpat daudz cik tiek izmantots kārtošanai ar sapludināšanu (merge sort). Papildus atmiņas prasība var būtiski ietekmēt algoritma darbības ātrumu un kešatmiņas darbību praktiskā algoritma pielietojumā. Lai novērstu vienkāršās versijas trūkumus ir izstrādāts ātrās kārtošanas algoritms, kurš spēj sakārtot datus vidēji izmantojot O(log n) papildus atmiņu. Ātrās kārtošanas algoritma dalīšanas funkcijas pseidokods izskatās sekojoši:

  function partition(array, left, right, pivotIndex)
        pivotValue := array[pivotIndex]
        swap array[pivotIndex] and array[right] // Pārvietot dalītāju uz beigām
        storeIndex := left
        for i  from  left to right - 1 // left ≤ i < right 
            if array[i] ≤ pivotValue
                swap array[i] and array[storeIndex]
                storeIndex := storeIndex + 1
        swap array[storeIndex] and array[right] // Pārvietot dalītāju uz tā gala pozīciju
        return storeIndex
Šis dalīšanas algoritma pseidokods nav tāds kādu to izstrādāja Čārlzs Antonijs Ričards Hoars, pastāv vēl citas dalīšanas funkcijas priekš ātrās kārtošanas algoritma, tomēr šo saprast ir nedaudz vieglāk kā citas.
Kad dalīšanas funkcija ir izveidota uzrakstīt ātrās kārtošanas algoritmu vairs nav tik sarežģīti un tas ir sekojošs:

  procedure quicksort(array, left, right)
       if right > left
           select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
           pivotNewIndex := partition(array, left, right, pivotIndex)
           quicksort(array, left, pivotNewIndex - 1)
           quicksort(array, pivotNewIndex + 1, right)
Tomēr tā, kā dalīšanas funkcija pārkārto elementus katrā daļā, tad šī ātrās kārtošanas algortima versija nav stabila.
Šī ir vēl viena ātrās kārtošanas algoritma versija, kas darbojas ar nelielu papildus atmiņu:

 function quicksort(array, left, right)
     var pivot, leftIdx = left, rightIdx = right
     if right - left > 0
         pivot = (left + right) / 2
         while leftIdx <= pivot and rightIdx >= pivot
             while array[leftIdx] < array[pivot] and leftIdx <= pivot
                 leftIdx = leftIdx + 1
             while array[rightIdx] > array[pivot] and rightIdx >= pivot
                 rightIdx = rightIdx - 1;
             swap array[leftIdx] with array[rightIdx]
             leftIdx = leftIdx + 1
             rightIdx = rightIdx - 1
             if leftIdx - 1 == pivot
                 pivot = rightIdx = rightIdx + 1
             else if rightIdx + 1 == pivot
                 pivot = leftIdx = leftIdx - 1
         quicksort(array, left, pivot - 1)
         quicksort(array, pivot + 1, right)

Dalītāja izvēle

Sākotnējā algoritma versijā par dalītāju tika izvēlēts kreisais pirmais elements no kārtojamo elementu saraksta, tomēr tāda dalītāja izvēle rada sliktākā varianta sarežģītību  gandrīz sakārtotiem failiem, kas ir diezgan bieža parādība praktiskā pielietojumā. Šī problēma tika novērsta par izveidojot dalīšanas funkciju, kas par dalītāju katru reizi izvēlas nejaušu elementu, vidējo elementu, vai pēdējo elementu no faila.