QuickSort

Z CHWiki

[editovat] Popis

Quick sort je v praxi asi najpoužívanejší triediaci algoritmus, kvôli jeho veľkej efektívnosti, jeho časová zložitosť v najhoršom prípadě je O(n²), v priemeru má ale zložitost O(n.log(n)) (pokud je pivot volen zcela náhodne). Je to rekurzívny algoritmus a je veľmi jednoduché ho implementovať. Z poľa sa vyberie jeden prvok (bude sa nazývať pivot) a všetky prvky, ktoré sú menšie od pivota, sa dajú naľavo a všetky väčšie prvky sa dajú napravo (pivot je po tomto na mieste, na ktorom bude aj na konci, keďže napravo sú všetky prvky väčšie a pri dalšom triedení sa nemajú ako dostať naľavo, to isté platí o prvkoch naľavo). Potom sa toto rekurzívne spraví aj pre všetky prvky naľavo od pivota a potom pre všetky prvky napravo od pivota.

[editovat] Príklad

Nasledujúci príklad pracuje inak ako program za ním, ale ukazuje jasnejšie princíp quick sortu. Zvýraznené čísla sú pivoty (všimnite si, že v druhom riadku každého kroku sú pred pivotom menšie čísla a za pivotom väčšie. Znakom x sú označené miesta, kde boli v niektorom z predchádzajúcich krokov pivoty a teda miesta, kde sú už umiestnené správne čísla.

pole pred triedením
  6 8 4 5 2 3 1 7 0 9
 
1. krok
  6 8 4 5 2 3 1 7 0 9	
  4 5 2 3 1 0 6 8 7 9	  
  
2.krok
  4 5 2 3 1 0 x 8 7 9
  2 3 1 0 4 5 x 7 8 9
  
3. krok	
  2 3 1 0 x 5 x 7 x 9
  1 0 2 3 x 5 x 7 x 9

4. krok 
  1 0 x 3 x x x x x x
  0 1 x 3 x x x x x x

5. krok 
  0 x x x x x x x x x
  0 x x x x x x x x x

výsledok
  0 1 2 3 4 5 6 7 8 9 

[editovat] Implementácia

function quickSort(pole, lavy, pravy)
    if lavy < pravy
        pivot := lavy
        for i := lavy + 1 to pravy
            if pole[i] < pole[lavy] 
                pivot := pivot + 1
                swap(pole[pivot], pole[i])
            end if
        end for
        swap(pole[pivot], pole[lavy])
        quickSort(pole, lavy, pivot)
        quickSort(pole, pivot + 1, pravy)
    end if
end function

Výsledná efektívnosť algoritmu závisí predovšetkých od voľby pivota, najčastejšie sa používa ľavý alebo pravý prvok. Efektívnejšie je ako pivot zvoliť medián ľavého, stredného a pravé prvku. Žiadne riešenie však nie je dokonalé.