Ātrās kārtošanas algoritms

thumb|320px|Ātrās kārtošanas algoritma darbības paraugs. Iekrāsotā vertikālā līnija ir dalītājs(pivot).

**Ātrās kārtošanas algoritms** ir kārtošanas algoritms, kuru 1960. gadā izstrādāja sers Čārlzs Antonijs Ričards Hoars (C.A.R. Hoare), britu datorzinātnieks, 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). Sliktākajā gadījumā algoritma sarežģītība ir {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) 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
Tas tika izstrādāts laikā, kad Hoars 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ā.

## Algoritms
right|200px|thumb|Pilns ātrās kārtošanas algoritma piemērs. Iekrāsotais elements ir dalītājs (pivot). Šajā piemērā katru reizi dalītājs izvēlēts kā pēdējais elements.

Algoritmam pamatā ir trīs soļi:
# Izvēlēties dalītāju (pivot) no faila.
# Pārkārtot failu tā, lai labajā pusē dalītājam (pivot) atrastos visi faila elementi, kas ir par to lielāki un kreisajā pusē visi elementi, kas ir mazāki.
# Rekursīvi izsaukt algoritmu katrai no izveidotajām faila daļām.

Algoritms ir balstīts uz ideju, ka apmaiņas darbības ieteicams veikt lielos attālumos, lai tās būtu visefektīvākās. Algoritma ātrdarbība lielā mērā atkarīga no tā, kādās daļās tiek sadalīts kārtojamais fails izpildot dalīšanas funkciju, kas savukārt atkarīgs no izvēlētā dalītāja (pivot). Ideāli būtu, ja katrā dalīšanas reizē fails tiktu sadalīts tieši uz pusēm, taču ne vienmēr ir pieejama nepieciešamā informācija, kuru elementu izvēlēties par dalīšanas elementu, lai panāktu ideālo sadalījumu. Nejaušam failam ir pilnīgi vienalga, kuru elementu izvēlas par dalīšanas elementu, jo ar jebkuru elementu kā dalīšanas elementu nejaušs fails tiks sadalīts vienādās daļās vidējā gadījumā.

### Vienkāršā versija
Vienkāršā pseidokodā algoritms var tikt izteikts sekojoši:
  **function** quicksort(masivs)
        **var** *list* mazaks, lielāks
        **if** length(masivs) ≤ 1
            **return** masivs
        select and remove a pivot value *pivot* from masivs
        **for each** x **in** masivs
            **if** x ≤ pivot **then** append x to mazaks
            **else** append x to lielāks
        **return** concatenate(quicksort(mazaks), pivot, quicksort(lielaks))

Jāievēro, ka vienkāršajā algoritma variantā elementi tiek pārbaudīti, tikai salīdzinot tos ar citiem elementiem, kas padara ātrās kārtošanas algoritmu par kārtošanu ar salīdzināšanu.

Algoritma pareizums ir balstīts uz sekojošiem argumentiem:
* Katrā iterācijā visi apstrādātie elementi nonāk to vēlamajā pozīcijā: mazākie pirms dalītāja (pivot), lielākie aiz dalītāja.
* Katra iterācija vismaz vienu elementu noliek tā galējā sakārtotajā pozīcijā.

### 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

right|200px|thumb|Ātrā kārtošana bez papildus atmiņas. Dalītājs (pivot) ir elements melnajā rāmī, zilās krāsas elementi ir mazāki vai vienādi, sarkanās krāsas elementi ir lielāki.

Š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 {O}(n^2) gandrīz sakārtotiem failiem, kas ir diezgan bieža parādība praktiskā pielietojumā. Šī problēma tika novērsta, 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.

## Analīze
Sākotnējā variantā nav pārāk grūti saprast, ka ātrā kārtošana izmanto vidēji \mathcal{O}(n \log n) laiku. Tas ir saprotams, jo ir redzams, ka dalīšanas funkcija, kura iet cauri failam tikai vienreiz, izmanto \mathcal{O}(n) laiku.

Labākajā sagaidāmajā variantā, katru reizi veidojot kārtojamā faila daļu, iepriekšējais fails tiek sadalīts divās aptuveni vienādās daļās, tas nozīmē, ka katrs rekursīvs izsaukums darbojas tikai ar pusi no iepriekšējā faila, līdz ar to var veikt tikai \log n izsaukumus pirms tiek sasniegts fails ar garumu 1. Tas nozīmē, ka katra algoritma izsaukuma dziļums ir vienāds ar \mathcal{O}(\log n). Nepastāv divi vienādi izsaukumi, kuri apstrādātu vienādu faila daļu, tādējādi katram izsaukuma līmenim nepieciešams tikai \mathcal{O}(n) laiks, rezultātā kopējais algoritms izmanto tikai \mathcal{O}(n \log n) laiku.

Alternatīvs novērtējuma variants ir izmantot rekurences (T(n)) aprēķinu - laiku, kas nepieciešams, lai sakārtotu n elementu garu failu. Rekurences aprēķina formula ir sekojoša:

:T(n) = \mathcal{O}(n) + 2T\left(\frac{n}{2}\right).

Pamatteorēmā savukārt minēts, ka rekurence ir T(n) = \mathcal{O}(n \log n).

Sliktākajā gadījumā savukārt abu izveidoto faila daļu garumi ir 1 un n-1 (piemēram, dalītājs ir vislielākais skaitlis kārtojamajā failā) līdz ar to izsaukumu skaits pieaug līdz n izsaukumiem. Tādā gadījumā rekurence ir sekojoša:
:T(n) = \mathcal{O}(n) + T(0) + T(n-1) = O(n) + T(n-1).
un rezultāts ir sekojošs:
T(n) = \mathcal{O}(n^2)

Nepieciešams atcerēties, ka pastāv vairāki ātrās kārtošanas algoritma varianti, tajā skaitā arī nerekursīvs ātrās kārtošanas algoritms, izvēle paliek lietotāja ziņā, tomēr labu rezultātu var iegūt, ja par dalītāju katru reizi izsaucot algoritmu tiek izvēlēts nejaušs elements no kārtojamo elementu faila. Tādējādi algoritmā nepieciešams mainīt dalīšanas funkciju, tomēr izmantojot uzlabotu ātrās kārtošanas algoritmu līdz minimumam tiek samazināta iespēja rezultātā iegūt sliktākā gadījuma algoritma sarežģītību {O}(n^2). 

## Varianti
Pastāv 3 labi zināmi ātrās kārtošanas algoritma varianti:
* **Balansētā ātrā kārtošana** dalītājs (pivot) katru reizi tiek piemeklēts tāds, lai tas būtu aptuveni tik liels kā vidējais elements no faila.
* **Ārējā ātrā kārtošana** tāds pats algortims kā parastais ātrās kārtošanas algoritms, tikai dalītājs tiek aizvietots ar buferi, fails tiek kārtots bufera atmiņā.
* **Trīs-virzienu radix ātrā kārtošana** (saukta arī **multikey ātrā kārtošana**) ir radix kārtošanas un ātrās kārtošanas apvienojums. Tiek izvēlēts elements no faila (dalītājs) un pirmais elementa simbols tiek izmantots kā atslēga. Atlikusī faila daļa tiek sadalīta 3 daļās: tādās, kuru atslēgas ir mazākas, vienādas vai lielākas ar dalītāja atslēgu. Rekursīvi tiek izsaukts algoritms daļām, kuru elementu atslēgas ir mazākas vai lielākas, pēc tam rekursīvi tiek izsaukts algoritms daļai, kurā elementu atslēgas bija vienādas, salīdzinot kārtojamo elementu otros simbolus.