Tato stránka obsahuje přehled třídících (řadících) algoritmů, které najdou uplatnění v celé řadě aplikací. Algoritmy pracují s celočíselným polem deklarovaným v programu jako typ TPole a třídí N prvků tohoto pole. Pro svoji potřebu si je můžete snadno upravit. Funkci algoritmu nejsnáze pochopíte, pokud si nakreslíte vstupní pole s čísly a provedete na něm pár počátečních kroků algoritmu, nebo si na něm alespoň zhruba vyznačíte okomentované kroky algoritmu.

Obsah

• Algoritmy vnitřního třídění
  1. Bubble sort
  2. Bubble sort (vylepšená verze)
  3. Třídění přímým výběrem minima
  4. Třídění přímým vkládáním
  5. QuickSort (rekurzivní)

Algoritmy vnitřního třídění

Vnitřní třídění je takové třídění, kdy předem známe tříděné prvky a máme k dispozici dostatek volné paměti, abychom je uvnitř této paměti mohli setřídit. Opakem je pak třídění vnější, kdy jednotlivé prvky předem neznáme a musíme je ze vstupu postupně načítat v pořadí, v jakém přicházejí. Toto třídění se provádí typicky v situacích, kdy máme operační paměti málo a nejsme schopni v ní všechny prvky uložit. Ve vnějším třídění proto využijeme vnější paměti - pracujeme s jednotlivými soubory na disku. Teoreticky tak můžeme setřídit daleko větší množství dat, operace s vnější pamětí jsou však také podstatně pomalejší. Práce se soubory rychlé algoritmy podstatně degraduje.

Úloha vnitřního třídění založeného na porovnávání dvou prvků má v nejhorším případě složitost O(n.log n) (to je výborná složitost HeapSortu). Některé algoritmy (QuickSort, nejrychlejší algoritmus v průměrném případě) mohou v ideálním případě dosáhnout i lineární složitosti, jiné zase dosahují složitostí vyšších (O(n²)).

Bubble sort (bublinkové třídění)

procedure BubbleSort(var pole:TPole; N:word);
var i,j, pom: integer;
begin
  for j:=1 to N-1 do {probublavani provadime pro n-1 prvku}
    for i:=1 to N-1 do {postupne pro vsechny prvky pred poslednim}
      if pole[i]>pole[i+1] then {pokud je prvek mensi nez nasledujici}
      begin {prehod prvky => probublavani vetsiho prvku polem}
        pom:=pole[i+1]; {prvky snadno prohodime pomoci pomocne promenne pom}
        pole[i+1]:=pole[i];
        pole[i]:=pom
      end
end;

Algoritmus postupně "bere" jednotlivé prvky pole (N-1 prvků) a posouvá je dále doprava, dokud jsou větší než prvek před nimi.

Pro začátek se podíváme podrobněji na určení složitosti algoritmu: Složitost algoritmu je evidentně O(n²), algoritmus prochází pole o N prvcích ve dvou vnořených cyklech, každý cyklus sestává přibližně z N operací (přibližně N operací pro každých N prvků, tj. celkem N²), počet výměn prvků a přiřazovacích operací ve vnitřním cyklu se projeví jako multiplikativní konstanta, kterou lze ve výsledku zanedbat (jedná se jen o konstantní operace, které jsou samy o sobě nezávislé na velikosti vstupních dat). Lepší složitosti se dá dosáhnout drobnými vylepšeními algoritmu. Pro velká vstupní data není složitost O(n²) nejvhodnější, nejrychlejší třídící algoritmus v nejhorším případě Heap sort (třídění haldou) dosahuje složitosti logaritmické. Přesto v jednoduchém případě můžeme tento algoritmus využít.

Vylepšený Bubble sort

procedure BubbleSort(var pole:TPole; N:word);
var i,j, pom: integer;
    konec: boolean;
begin
  for j:=1 to N-1 do
  begin {probublavani provadime pro n-1 prvku}
    konec:=true; {pred zacatkem vnitrniho cyklu nastavime konec na true}
    for i:=1 to N-1 do {postupne pro vsechny prvky pred poslednim}
      if pole[i]>pole[i+1] then {pokud je prvek mensi nez nasledujici}
      begin {prehod prvky => probublavani vetsiho prvku polem}
        pom:=pole[i+1];
        pole[i+1]:=pole[i];
        pole[i]:=pom;
        konec:=false {s prvkem se provedla vymena}
      end;
    if konec then Break {pokud nebyl ani jeden prvek v cyklu vymenen,
                         tj. vsechny prvky byly uz na svem miste,
                         ukoncime trideni (bylo by zbytecne setridene
                         prvky dale prochazet}
  end
end;

Složitost algoritmu v nejhorším případě zůstává stejná (O(n²)), pokud je však vstupní pole už relativně setříděné, často si ušetříme zbytečné automatické procházení tím, že si zaznamenáme průchod, v kterém byly už všechny prvky umístěné ve správném pořadí - konec třídění.

Třídění přímým výběrem minima

procedure PrimyVyber(var pole:TPole; N:word);
var i,j, min, pom: integer;
begin
  for i:=1 to N-1 do {na tyto pozice budeme vybirat minimum}
  begin
    min:=i; {nastaveni pozice minima}
    for j:=i+1 to N do  {vyhledani mozneho minima v dalsich prvcich}
      if pole[j]<pole[min] then min:=j;
    if pole[min]<pole[i] then {pokud byl nalezen mensi prvek}
    begin                     {-> provedeni vymeny prvku}
      pom:=pole[i];
      pole[i]:=pole[min];
      pole[min]:=pom
    end
  end
end;

Algoritmus postupně prochází pole a na dané místo hledá minimum ze zbývajících prvků. Ve for cyklu se prochází postupně
(n-1) + (n-2) + (n-3) + ... + 1 prvků, tj. po sečtení (n²-n)/2, řádově je tedy složitost opět O(n²).

Třídění přímým vkládáním

procedure PrimeVkladani(var pole:TPole; N:word);
{prvky postupne zarazujeme do leve casti pole - vytvarime setridene pole}
var i,j, pom: integer;
begin
  for i:=2 to N do {prochazime nesetridenou cast pole}
  begin
    pom:=pole[i]; {ulozime si zatrizovany prvek}
    for j:=i-1 downto 1 do {tento i-ty prvek zarazujeme do leve setridene casti pole}
      if pole[j]>pole[j+1] then begin {jestlize je prvek vlevo vetsi, prvky prehodime}
        pole[j+1]:=pole[j];
        pole[j]:=pom
      end
  end
end;

Algoritmus prvky z pravé části pole přímo zatřiďuje do levé části, kde se utváří seřazená posloupnost, postupně procházíme
1 + 2 + 3 + 4 + 5 + ... + (n-1) prvků jako v minulém případě, složitost je tedy také O(n²), jediný rozdíl tkví v tom, že tento způsob manipuluje při řazení přímo s jednotlivými prvky a ne jenom s jejich indexy.

QuickSort (rekurzivní)

procedure QuickSort(var pole:TPole; Zac,Kon:integer);
{procedura setridi v poli usek od indexu Zac do indexu Kon}
var P: integer; {hodnota pro rozdeleni pole na useky - pivot}
    pom: integer; {pomocna promenna pro vymenu prvku}
    i,j: integer; {pracovni indexy pro vymezeni casti pole}
begin
  i:=Zac; {na zacatku zabiraji mezni indexy cele pole}
  j:=Kon;
  P:=pole[(Zac+Kon) div 2]; {urcime si pivotni prvek - vezmeme prostredni prvek pole}
                            {idealni pivot by byl median - prostredni z hodnot v poli}
  repeat                    {nalevo od pivota budeme radit mensi prvky, napravo vetsi prvky nez pivot}
    while pole[i]<P do inc(i); {posouv me levě index, dokud neni na prvku vetsim nez pivot}
    while pole[j]>P do dec(j); {posouvame pravy index, dokud neni na prvku mensim nez pivot}
    if i<j then {pokud se indexy neprekrizily a nejsou shodne}
    begin
      pom:=pole[i]; {vymenime nalezene prvky}
      pole[i]:=pole[j];
      pole[j]:=pom;
      inc(i); dec(j); {a posuneme indexy na dalsi prvky}
    end
    else if i=j then {pokud se indexy sesly (ukazuji na pivota)}
    begin
      inc(i); {posunume je jeste dale, aby vymezovaly roztridene poloviny pole}
      dec(j); {a doslo k prekrizeni, coz vede k ukonceni cyklu}
    end
  until i>j; {opakujeme, dokud nejsou obeti casti pole roztrideny podle pivota}
  {Pole [Zac,Kon] je rozdeleno na 2 useky [Zac,j] a [i,Kon],
   ktere zpracujeme rekurzivne (opet touto procedurou)}
  if Zac<j then QuickSort(pole,Zac,j); {ma smysl tridit nejmene dva prvky}
  if i<Kon then QuickSort(pole,i,Kon);
end;

Funkce algoritmu je dostatečně zřejmá z komentářů, takže stručně o co jde: QuickSort vychází z rekurzivního přístupu: Pokud máme třídit elementární pole o dvou prvcích, prvky jednoduše přehodíme na tu stranu, kam patří (porovnat je můžeme s pomyslnou hodnotou mezi nimi - pivotním prvkem). Pokud máme třídit pole větší, roztřídíme takto podle zvoleného pivota i dva velké úseky pole, které potom dále necháme třídit rekurzivně stejnou procedurou, až budou nakonec uspořádány všechny části pole. Tento algoritmus je typickým příkladem použití metody "rozděl a panuj" (Divide & Impera), kdy programátor daný problém rozdělí na více jednoduchých elementárních problémů, které lze snadno vyřešit (třeba rekurzí). Pokud si vzpomenete na tento princip a vybavíte si postup, určitě pak budete schopni jednotlivé detaily algoritmu snadno doprogramovat.

Průměrná složitost QuickSortu je O(n.log n), přesněji O(n.log₂n), nejlepší složitost O(n) nastává, pokud je vždy ideálně vybrán pivot jako prvek s prostřední hodnotou, nejhorší případ O(n²) nastává, pokud je pivot vždy nešikovně vybrán jako hodnota maximální nebo minimální. Výše uvedená procedura vybírá pivotní prvek jako střed pole, záleží ale na rozložení vstupních dat, každý z prvků pole je pro určitou kombinaci ideální, výběr se proto někdy provádí náhodně (pomocí generátoru náhodných čísel), což zaručuje, že při různém výběru pivotů nebude volba pro vstupní data vyloženě nevhodná a složitost se tak více přiblíží k očekávané složitosti O(n.log n). V průměrném případě se v pravé a levé části pole zaměňuje vždy polovina prvků: Pro jednotlivé zmenšující se úseky tedy n/2, n/4, n/8, n/16 ... a vzhledem k tomu, že po záměně prvků se každé pole rozdvojuje na dvě poloviny (políčka si můžeme nakreslit do vyváženého binárního stromu), je složitost násobena dvojkovým logaritmem (zhruba zapisujeme jen logaritmus desítkový).Výsledná průměrná složitost je tedy intuitivně:

---