Bakalářská práce

České vysoké učení technické v Praze

Fakulta jaderná a fyzikálně inženýrská

Aplety:

Nejčastější označení, pod kterým se s tímto algoritmem setkáme, je quicksort . Vedle českého překladu rychlé třídění se také setkáme s označením třídění rozdělováním. Algoritmus pro rychlé vnitřní třídění publikoval Hoare a jak se bystrý čtenář podle názvu jistě dovtípil, je (alespoň ve většině případů) velmi rychlý.

Myšlenka tohoto algoritmu vychází ze skutečnosti, že nejefektivnější jsou výměny prvků v poli na velké vzdálenosti. Jestliže např. vezmeme pole s n prvky seřazenými v obráceném pořadí, můžeme je utřídit pomocí pouhých n/2 výměn. Porovnáme prvky na obou koncích pole a zamě­níme je; pak postoupíme o jedno pole směrem ke středu a zopakujeme porovnání.

Pokud pole není seřazené v obráceném pořadí, nemůže být náš postup tak přímočarý. Vyjdeme z principu rozděl a panuj.

Zvolíme náhodně prvek x a uspořádáme pole a tak, aby vlevo od x ležely prvky s klíči menšími než je klíč x a vpravo prvky s klíči většími než je klíč x. Tím jsme pole rozdělili na tři části. Prvek x je již na svém místě, vlevo od něj jsou prvky menší a vpravo od něj jsou prvky větší.

Pokud pole obsahuje pouze 3 prvky a za x jsme zvolíme prostřední (prostřední pokud jde o velikost, tedy medián ), získáme tímto procesem uspořádané pole. Pokud má pole délku 2, můžeme za x zvolit kterýkoli z nich - výsledkem bude opět uspořádané pole.

Odtud je již zřejmý algoritmus rychlého třídění:

Zvolíme x a rozdělíme popsaným způsobem tříděné pole na úseky a[1], ... , a[s], ..., a[n]. Přitom platí, že a[s] = x, prvky a[1], ... , a[s-1] jsou menší nebo rovny x a prvky  a[s+1], ... , a[n] jsou větší nebo rovny x.

Proces rozdělení opakujeme pro úseky  a[1], ... , a[s] a a[s+1], ... , a[n] a dále pak pro jejich části, až dospějeme k úsekům délky 1. Ty jsou již automaticky utříděné.

Rozdělení pole na dvě části

Podívejme se nyní podrobněji na proces rozdělení pole na dvě části.

Z toho, co jsme si řekli v předchozím oddílu, plyne: vyjdeme od prvního prvku pole a a budeme hledat prvek, který je větší než x (má větší klíč). Zároveň budeme pole a prohledávat od konce, až narazíme na prvek, který je menší než x. Pak tyto dva prvky zaměníme. Až se oba směry prohledávání setkají uprostřed pole, skončíme.

Vzhledem k tomu, že se s takovýmto dělením pole na dvě části setkáme také v následujícím oddílu, věnovaném hledání mediánu, formulujeme je jako samostatnou  proceduru:

type pole = array [1..n] of prvek;

procedure Rozděl(var a: pole, x: prvek);

var w:   prvek;

    i,j: index;

begin

  i := 1; j := n;

  repeat                           {Tyto dva cykly while hledají}

    while a[i].klíč < x.klíč do inc(i);         {prvky, které se}

    while x.klíč < a[j].klíč do dec(j);         {navzájem vymění}

    if i <= j then begin

      w := a[i]; a[i] := a[j]; a[j] := w;                {Výměna}

      inc(i); dec(j);

    end

  until i > j;                     {Až do setkání uprostřed pole}

end;

Příklad 8.1

Uvažujme posloupnost

                                               (17, 12, 15, 11, 20, 13).

Za rozdělovací prvek x zvolíme hodnotu 15. První cyklus while najde prvek 17, který je větší než x a leží vlevo od x. Druhý cyklus while najde prvek 13, který je menší než x a leží vpravo od x. Proto se tyto dva prvky zamění. Tak dostaneme posloupnost

                                               (13, 12, 15, 11, 20, 17).

Dále první cyklus while skončí u hodnoty 15 (tedy u prvku x) a druhý cyklus while u hodnoty 11. Po výměně těchto prvků bude mít naše posloupnost tvar

                                               (13, 12, 11, 15, 20, 17).

Tím procedura rozdělování skončí. Všimněte si, že se přemístila i zarážka x.

Poznamenejme, že v algoritmu pro rychlé třídění použijeme lehce upravenou verzi této procedury.

Vlastní algoritmus rychlého třídění

Vlastní implementace algoritmu quicksort bude již velice jednoduchá. Základem bude rekurzivní (nebo iterativní) volání lehce upravené rozdělovací  procedury.

V následující proceduře budeme pro změnu předpokládat, že pole třídíme na základě hodnot funkce Pořadí(X: prvek):integer. Pokud bychom chtěli třídit podle klíčů, stačí výrazy tvaru Pořadí(a[i]) nahradit výrazy tvaru a[i].klíč.

Procedura Třídění, vnořená do procedury Quicksort, je vlastně stará známá procedura Rozděl, která má jako vstupní parametry počáteční a koncový index tříděného úseku pole. Jako x, prvek, podle kterého se pole rozděluje, se volí vždy prostřední prvek. Na konec této procedury jsme doplnili rekurzivní volání: jestliže po rozdělení vzniknou úseky delší než 1, zavolá se na ně opět procedura Třídění.

Vlastní tělo procedury Quicksort obsahuje pouze volání procedury Třídění pro celé pole, tedy pro úsek od indexu 1 do n.

procedure Quicksort;                           {Rekurzivní verze}

      {procedura Třídění rozděluje pole na úseky a ty uspořádává}

                              {třídí úsek pole a od a[l] do a[r]}

  procedure Třídění(l,r: index);

  var w,x: prvek;

      i,j: index;

  begin {Třídění}

      i := l; j := r;

      x := a[(l+r) div 2];             {Zarážka: prvek uprostřed}

      repeat

        while Pořadí(a[i]) < Pořadí(x) do inc(i);

                                        {Indexy prvků pro výměnu}

        while Pořadí(a[j]) > Pořadí(x) do dec(j);

        if i <= j then begin                             {výměna}

           w := a[i]; a[i] := a[j]; a[j] := w;

           inc(i); dec(j);

        end

      until i>j;

      if l < j then Třídění (l,j);        {prvek x na svém místě}

      if i < r then Třídění (i,r);             {třídí se ostatní}

  end; {třídění}

begin {Quicksort}

    Třídění(1,n);

end;{Quicksort}

Použití rekurze v algoritmu rychlého třídění je přirozeným důsledkem použití principu rozděl a panuj. Ve skutečnosti ale nemusí být rekurzivní tvar procedury Quicksort výhodný. Můžeme převést Quicksort do nerekurzivní podoby. Často je ovšem výhodnější vyjít z rozboru algoritmu a pokusit se dospět k nerekurzivní verzi přímo.

V našem případě je zřejmé, že při každém průchodu, tj. při každém volání procedury Třídění, se pole rozdělí na dva úseky. Jeden z nich můžeme ihned zpracovat, meze druhého si musíme uschovat. K tomu použijeme zásobník .

Na počátku vložíme do zásobníku meze celého pole, tj. 1 a n. Procedura QuicksortN (nerekurzivní quicksort) si tyto hodnoty ze zásobníku vezme, úsek pole rozdělí, jednu dvojici mezí uloží do zásobníku a druhou ihned zpracuje.

Zpracování bude probíhat v cyklu repeat, který skončí, jakmile nebude v zásobníku žádná další dvojice mezí ke zpracování.

Zásobník bude pole, složené ze struktur, obsahujících dvojice indexů. Definujeme jej jako objektový typ:

type  zásobník = object

       z: array [1..m] of record           {Pole na ukládání dat}

          l,r: index end;

       s: 0..m;                    {Ukazatel na vrchol zásobníku}

       constructor Vytvoř;

       procedure Vlož(i,j: index);

       procedure Vyjmi(var i,j: index);

       function Prázdný: boolean;

     end;

Konstruktor Vytvoř uloží do atributu s hodnotu 0 (zásobník je prázdný). Metody Vlož resp. Vyjmi umožňují vložit do zásobníku dvojici indexů resp. vyjmout ji ze zásobníku. Booleovská funkce Prázdný vrátí true, bude-li zásobník prázdný, tj. bude-li s = 0. Implementace těchto metod je triviální a přenechávám ji čtenáři.

V proceduře deklarujeme zásobník jako lokální proměnnou z typu zásobník. Při třídění se budeme - podobně jako v rekurzivní verzi - opírat o funkci Pořadí.

procedure QuicksortN;                        {Nerekurzivní verze}

var i,j,l,r: index;

    x, w:    prvek;

    z:       zásobník;

begin

 z.Vytvoř;

 z.Vlož(1,n);                            {Inicializace zásobníku}

 repeat                          {Další úsek z vrcholu zásobníku}

   z.Vyjmi(l,r);

   repeat                            {Rozdělení úseku a[l]..a[r]}

     i := l; j := r;

     x := a[(l+r) div 2];                               {Zarážka}

     repeat

       while Pořadí(a[i]) < x do inc(i); {Indexy prvků pro výměnu}

       while Pořadí(a[j]) > x do dec(j);

       if i <= j then begin                              {Výměna}

          w := a[i]; a[i] := a[j]; a[j] := w;

          inc(i); dec(j);

       end

     until i>j;

     if i < r then z.Vlož(i,r);    {Ulož pravý úsek do zásobníku}

     r := j

   until l >= r

 until z.Prázdný;

end;

V implementaci nerekurzivní verze algoritmu rychlého třídění zůstal jeden nevyřešený problém: jak velké má být m, konstanta, která určuje velikost zásobníku? Odpověď najdeme při analýze algoritmu rychlého třídění.

Analýza rychlého třídění

Vyjdeme od analýzy procesu rozdělování pole na úseky. Má-li tříděné pole n prvků, potřebujeme k rozdělení pole nejvýše n porovnání v cyklech while, kde porovnáme všechny prvky se zvolenou zarážkou x.

Dále určíme střední počet výměn. Bez újmy na obecnosti můžeme předpokládat, že tříděné pole obsahuje klíče 1, ... , n. Všechny permutace klíčů, tedy všechna možná uspořádání prvků v poli, pokládáme za stejně pravděpodobné. Jako zarážku x jsme zvolili prvek s klíčem i. Potom bude potřebný počet výměn roven součinu počtu prvků v levém úseku pole, i-1, a pravdě­podobnosti výskytu klíče, který je větší než i (a tedy jej musíme vyměnit). Tato pravděpodobnost je rovna počtu takových klíčů, lomenému n.

Střední počet výměn při dělení pole na úseky potom bude

                                                                                (11)

Kdyby se nám podařilo při volbě rozdělovacího prvku x zvolit vždy medián, tj. kdyby bylo výsledkem vždy rozdělení pole na poloviny, potřebovali bychom k utřídění pole log2n průchodů. To znamená, že v tomto (nejvýhodnějším) případě potřebujeme celkem C = n.log2n porovnání a M = (n/6).log2n výměn, tedy (n/2).log2n přesunů, neboť jedna výměna prvků vyžaduje tři přesuny.

Lze ukázat, že pokud budeme rozdělovací prvek volit náhodně (rovnoměrně), bude průměrná účinnost algoritmu rychlého třídění horší o faktor 2.ln 2.

Podívejme se ještě na nejhorší případ. Jeho analýza je zajímavá nejen z hlediska účinnosti algoritmu, ale i z hlediska velikosti zásobníku (konstanty m) v nerekurzivní verzi.

Zřejmě nejhorší možný případ nastane, jestliže jako zarážku zvolíme nejmenší prvek z dané­ho úseku. Potom bude mít pravý úsek délku n - 1 prvků a levý délku 1. Pokud se nám takováto nešťastná volba podaří v každém kroku, budeme potřebovat místo log₂n celkem n rozdělení. V tomto případě bude celkový počet porovnání i přesunů O(n²) a rychlé třídění již nebude dělat čest svému jménu.

Zmíněný nejhorší případ nastane mj. tehdy, když bude pole již předem utříděné a my budeme volit jako x vždy první nebo poslední prvek. Pokud bychom volili vždy prostřední prvek, představovalo by utříděné pole naopak nejlepší případ; čtenář ovšem jistě snadno zkonstruuje pole, které povede k nejhoršímu případu při volbě prostředního prvku.

Obvykle se doporučuje buď volit x náhodně nebo jako medián malého vzorku (3 - 5 prvků). Taková volba sice nezmění průměrný výkon algoritmu, zlepší ale jeho chování v nejhorším případě.

Podívejme se nyní na nerekurzivní verzi algoritmu. Délka zásobníku musí vycházet z nejhor­šího možného případu. V proceduře QuicksortN vždy zpracováváme levý úsek a meze pravého úseku uložíme do zásobníku, kde čekají na budoucí zpracování. Jestliže bude mít pravý úsek vždy délku 1 a levý n - 1, nahromadí se nám v zásobníku až n dvojic mezí. To znamená, že v nejhorším případě může být potřeba pomocné paměti O(n)!

Přitom pro rekurzivní proceduru nebude situace o nic lepší - naopak, spotřeba paměti bude ještě vyšší. Jak víme, budou se parametry rekurzivních volání ukládat na implicitní zásobník programu; vedle toho ovšem přibudou ještě lokální proměnné a návratové adresy.

Vraťme se ale k nerekurzivní verzi. Snadno ukážeme, že když budeme  vždy zpracovávat jako první kratší úsek a delší odložíme na později, bude maximální délka zásobníku rovna m = log₂n (to nastane, jestliže budeme za x volit vždy medián). Odpovídající úpravu procedury QuicksortN zvládne čtenář jistě sám.

Poslední aktualizace: 29-05-2003.