Skip to main content.

Zaradenie a popis

Quicksort alebo triedenie rozdeľovaním je jeden z najrýchlejších známych triediacich algoritmov, založených na porovnávaní prvkov. Jeho priemerná doba výpočtu je O(n.logn) a je najlepšia zo všetkých podobných algoritmov. Jeho naprogramovanie je aj celkom jednoduché. Nevýhodou je, že pri nevhodnom usporiadaní vstupných dát môže byť časová a pamäťová náročnosť tohto algoritmu až O(n2).

Napriek tomu, že Quicksort nemá zaručenú časovú zložitosť O(n.logn), reálne aplikácie a testy ukazujú, že na pseudonáhodných vstupných údajoch je najrýchlejší zo všetkých všeobecných triediacich algoritmov. To znamená rýchlejší ako Heapsort a Mergesort, ktoré sú formálne rýchlejšie. Maximálna časová náročnosť O(n2) však nedovoľuje jeho použitie v kritických aplikáciách.

^ TOP

Motivácia a špecifikácia

Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať túto postupnosť vzostupne v priemernom čase O(n log n).
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A

^ TOP

Myšlienka algoritmu

Quicksort je algoritmus používajúci techniku divide and conquer. Rozdeľuje pole nasledujúcim spôsobom: vyberie sa jeden prvok nazývaný pivot a presunú sa všetky prvky menšie ako pivot naľavo od neho a všetky prvky väčšie ako pivot napravo. Potom tento proces rekurzívne spustíme na pravej a ľavej časti poľa. Algoritmus končí vnáranie vtedy, keď dostane utriediť podpole veľkosti 2 (prípadne 1) a začína sa vynárať. Keď sa vynoria všetky vnorenia rekurzie, je pole utriedené.

Proces výmeny prvkov je možné robiť efektívne v lineárnom čase a na mieste. Keď je vybraný medián x, prehľadávajú sa prvky zľava, pokiaľ sa nenájde prvok a>x, potom sa prehľadávajú prvky sprava, pokiaľ sa nenájde prvok b<x. Tieto prvky sa vymenia a pokračuje proces prehľadávania a výmeny, pokiaľ sa pravé a ľavé prehľadávania nestretnú.

^ TOP

Vizualizácia

Quicksort - animácia Quicksort - pivot

^ TOP

Zápis algoritmu

    procedure quicksort (l,r : integer);
    var i,j,x,w : integer;                    
    begin
      i:=l; j:=r;
      x:=akt[(l+r) div 2];
      repeat
        while akt[i] < x do i:=i+1;
        while x < akt[j] do j:=j-1;
        if i <= j then begin
          w:=akt[i];
          akt[i]:= akt[j];
          akt[j]:=w;
          i:=i+1; j:=j-1
        end
      until i > j;
      if l < j then quicksort(l,j);
      if i < r then quicksort(i,r)
    end;
^ TOP

Vlastnosti algoritmu

Čas behu algoritmu je v priemernom prípade O(n log n). Dobrá časová zložitosť algoritmu spočíva v správnom výbere pivota. V ideálnom prípade je to medián (alebo hodnota blízka mediánu).Ak však je pivot zakaždým minimum alebo maximum daného podpoľa, časová zložitosť narastá na O(n2).
Preto je vhodné použiť na výber pivota jednu z nasledujúcich techník:
 a) Náhodný prvok – často používaná metóda. Ak ide o naozaj náhodný výber, čas triedenia je O(n log n).
 b) Metóda mediánu z troch čísel (prípadne z ľubovolného konštantného počtu) – vyberú sa z množiny tri prvky, z ktorých sa nájde medián a ten sa zvolí za pivota.
Qucksort nie je stabilné triedenie a triedi prvky in-situ.

^ TOP

Experimentovanie

Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

College of Engineering, The University of Texas, USA
Quicksort spracovaný do java appletu.
http://www-cse.uta.edu/~holder/courses/cse2320/lectures/applets/quicksort/

^ TOP