Třídící algoritmy


Třídící algoritmy dělíme na algoritmy vnitřního a algoritmy vnějšího třídění. Obvykle třídíme exempláře datové struktury typu pascalského záznamu. V takové datové struktuře bývá obsažena jedna význačná položka, klíč, podle které se záznamy řadí. Pro zjednodušení budeme předpokládat, že třídíme záznamy obsahující pouze klíč, který je celočíselný – budeme tedy třídit pole celých čísel. Pomocí počtu tříděných čísel N pak budeme vyjadřovat časovou (a paměťovou) složitost jednotlivých algoritmů.

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.

Časová složitost algoritmů v číslech

 

četnost /

počet klíčů

10 20 50 1000
log n 0,000001s 0,000001s 0,000002s 0,000003s
n 0,00001s 0,00002s 0,00005s 0,001s
n2 0,0001s 0,0004s 0,0025s 1s
2n 0,001024s 1,048576s 35,7 let 3,4∙10287 let
nn 2,8 hodiny 3∙1012 let 2,8∙1071 let 3,2∙102986 let

 

Vlastnosti


Třídící metoda se nazývá stabilní, když zachovává relativní uspořádání záznamů se stejným klíčem (důležité při utřídění záznamů podle sekundárních klíčů).

Třídící algoritmus nazýváme přirozeným, jestliže jeho složitost roste resp. klesá v závislosti na míře původní setříděnosti vstupní posloupnosti. Vazba na rychlost.
 

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


Nejjednodušší třídící algoritmy patří do skupiny přímých metod. Všechny mají několik společných rysů. Jsou krátké, jednoduché a třídí přímo v poli (nepotřebujeme pomocné pole). Ú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(n2)). Z toho vyplývá, že jsou použitelné tehdy, když tříděných dat není příliš mnoho. Na druhou stranu pokud je dat opravdu málo, je zbytečně složité používat některý z komplikovanějších algoritmů, které si předvedeme později.

 

Třídění přímým výběrem (SelectSort)


je založeno na opakovaném vybírání nejmenšího čísla z dosud nesetříděných čísel. Nalezené číslo prohodíme s prvkem na začátku pole a postup opakujeme, tentokrát s nejmenším číslem na indexech 2,…,N, které prohodíme s druhým prvkem v poli. Poté postup opakujeme s prvky s indexy 3,… ,N, atd. Je snadné si uvědomit, že když takto postupně vybíráme minimum z menších a menších intervalů, setřídíme celé pole (v i-tém kroku nalezneme i-tý nejmenší prvek a zařadíme ho v poli na pozici s indexem i).

procedure SelectSort(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]       if pole[min]           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í (n2-n)/2, řádově je tedy složitost opět O(N2).

 

Třídění přímým vkládáním (InsertSort) 


funguje na podobném principu jako třídění přímým výběrem. Na začátku pole vytváříme správně utříděnou posloupnost, kterou postupně rozšiřujeme. Na začátku i-tého kroku má tato utříděná posloupnost délku i-1. V i-tém kroku určíme pozici i-tého čísla v dosud utříděné posloupnosti a zařadíme ho do utříděné posloupnosti (zbytek utříděné posloupnosti se posune o jednu pozici doprava). Není těžké si rozmyslet, že každý krok lze provést v čase O(N). Protože počet kroků algoritmu je N, celková časová složitost právě popsaného algoritmu je opět O(N2).

procedure InsertSort(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(n2), 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.
 

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


pracuje jinak než dva dříve popsané algoritmy. Algoritmu se říká "bublinkový", protože podobně jako bublinky v limonádě "stoupají" vysoká čísla v poli vzhůru. Postupně se porovnávají dvojice sousedních prvků, řekněme zleva doprava, a pokud v porovnávané dvojici následuje menší číslo po větším, tak se tato dvě čísla prohodí. Celý postup opakujeme, dokud probíhají nějaké výměny. Protože algoritmus skončí, když nedojde k žádné výměně, je pole na konci algoritmu setří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(N2), 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 N2), 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(N2) 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;

Správnost algoritmu nahlédneme tak, že si uvědomíme, že po i průchodech while-cyklem bude posledních i prvků obsahovat největších i prvků setříděných od nejmenšího po největší (rozmyslete si, proč tomu tak je). Popsaný algoritmus se tedy zastaví po nejvýše N průchodech a jeho celková časová složitost v nejhorším případě je O(N2), neboť na každý průchod spotřebuje čas O(N). Výhodou tohoto algoritmu oproti předchozím dvěma algoritmům je, že pokud je pole na začátku setříděné, tak algoritmus spotřebuje jen lineární čas, O(N).

  

Třídění sléváním (MergeSort)


Lepší třídící algoritmy pracují v čase O(N log N). Jedním z nich je Třídění sléváním (MergeSort), založené na principu slévání (spojování) již setříděných posloupností dohromady. Představme si, že již máme dvě setříděné posloupnosti a chceme je spojit dohromady. Jednoduše stačí porovnávat nejmenší prvek z každé posloupnosti, který jsme dosud nedali do nově vytvářené posloupnosti, a menší z těchto prvků do nové posloupnosti přidat. Je zřejmé, že ke slití dvou posloupností potřebujeme čas úměrný součtu jejich délek.

My si zde popíšeme a předvedeme modifikaci algoritmu MergeSort, která používá pomocné pole. Algoritmus lze implementovat při zachování časové složitosti i bez pomocného pole, ale je to o dost pracnější. Existuje též modifikace algoritmu, která má počet fází (viz dále) v nejhorším případě O(log N), ale pokud je již pole na začátku setříděné, proběhne pouze jediná a v takovém případě má algoritmus časovou složitost O(N). My si však zatajíme i tuto variantu.

Algoritmus pracuje v několika fázích. Na začátku první fáze tvoří každý prvek jednoprvkovou setříděnou posloupnost a obecně na začátku i-té fázi budou mít setříděné posloupnosti délky 2i-1. V i-té fázi tedy vždy ze dvou sousedních 2i-1-prvkových posloupností vytvoříme jedinou délky 2i. Pokud N není násobkem 2i, bude délka poslední posloupnosti zbytek po dělení N číslem 2i. Zastavíme se, pokud 2i>= N, tj. po ceil(log2 N) fázích. Protože v i-té fázi slijeme ceil(N/2i) dvojic nejvýše 2i-1-prvkových posloupností, je časová složitost jedné fáze O(N). Celková časová složitost popsaného algoritmu je pak O(N log N).

procedure MergeSort(var A: Pole);
  var P: Pole; { pomocné pole }
  delka:integer; { délka setříděných posl. }
  i: integer; { index do vytvářené posl. }
  i1,i2: integer; { index do slévaných posl. }
  k1,k2: integer; { konce slévaných posl. }
begin
  delka:=1; 
  while delka       begin
          i1:=1; i2:=delka+1; i:=1;
          k1:=delka; k2:=2*delka;
          while i<=N do
              begin
                  if k2>N then k2:=N;
                      while (i1<=k1) or (i2<=k2) do
                  if (i1>k1) or
                  ((i2<=k2) and (A[i1]<=A[i2]))
                  then
                      begin
                          P[i]:=A[i1]; i:=i+1; i1:=i1+1;
                      end;
                  else
                      begin
                          P[i]:=A[i2]; i:=i+1; i2:=i2+1;
                      end;
                  i1:=k2+1; i2:=k2+delka;
                  k1:=k2+delka;
                  k2:=k2+2*delka;
              end;
          A:=P;
          delka:=2*delka;
      end;
end;

Quik Sort (rekurzivně)


V čase O(N log N) pracuje také algoritmus jménem QuickSort. Tento algoritmus je založen na metodě Rozděl a panuj. Nejprve si zvolíme nějaké číslo, kterému budeme říkat pivot. Více si o jeho volbě povíme později. Poté pole přeuspořádáme a rozdělíme je na dvě části tak, že žádný prvek v první části nebude větší než pivot a žádný prvek v druhé části naopak menší. Prvky v obou částech pak setřídíme rekurzivním zavoláním téhož algoritmu. Musíme ale dát pozor, aby v každém kroku obě části byly neprázdné (a rekurze tedy byla konečná). Je zřejmé, že po skončení algoritmu bude pole setříděné.Nejlepší volbou pivota by tedy byl medián tříděného úseku, tj. prvek takový, jenž by byl v setříděném poli přesně uprostřed. Přeuspořádání jistě zvládneme v lineárním čase a pokud by pivoty na všech úrovních byly mediány, pak by počet úrovní rekurze byl O(log N) a celková časová složitost O(N log N) (na každé úrovni rekurze je součet délek tříděných posloupnosti nejvýše N). Ačkoli existuje algoritmus, který medián pole nalezne v čase O(N), v QuickSortu se obvykle nepoužívá, jelikož konstanta u členu N je příliš velká v porovnání s pravděpodobností, že náhodná volba pivota algoritmus příliš zpomalí. Většinou se pivot volí náhodně z dosud nesetříděného úseku.

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]

  while pole[j]>P do dec(j); {posouvame pravy index, dokud neni na prvku mensim nez pivot}
  if i       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   if i end;

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.log2n), 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(n2) 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ě:

log n (n/2 + n/4 + n/8 + n/16 + ...) = n.log n

Dalšími třídícími algoritmy se složitostí O(n2) jsou:

 
 
Třídění počítáním (CountSort)


Toto třídění lze použít, pokud tříděné objekty obsahují pouze klíče a možných hodnot klíčů je málo. Tehdy stačí si spočítat, kolikrát se který klíč vyskytuje, a místo třídění vytvořit celé pole znovu na základě toho, kolik jednotlivých objektů obsahovalo pole původní. My si tento algoritmus předvedeme na příkladu třídění pole celých čísel z intervalu :

    const D = 1;
            H = 10;
 procedure CountSort(var A: Pole);
  var C: array[D..H] of integer;
  i,j,k: integer;
begin
  for i:=D to H do C[i]:=0;
  for i:=1 to N do C[A[i]]:=C[A[i]] + 1;
  k:=1;
  for i:=D to H do
  for j:=1 to C[i] do
      begin
          A[k]:=i;
          k:=k+1;
      end;
end;

Časová složitost takovéhoto algoritmu je lineární v N, ale nesmíme zapomenout přičíst ještě velikost intervalu, ve kterém se prvky nacházejí (K=H-D+1), protože nějaký čas spotřebujeme i na inicializaci pole počítadel. Celkem tedy O(N + K).
 

Přihrádkové třídění (BucketSort)


Pokud by tříděné objekty obsahovaly vedle klíčů i nějaká data, můžeme je místo pouhého počítání rozdělovat do přihrádek podle hodnoty klíče a pak je z přihrádek vysbírat v rostoucím pořadí klíčů. Tomuto algoritmu se říká přihrádkové třídění (BucketSort) a my si popíšeme jeho víceprůchodovou variantu (RadixSort), která je vhodnější pro větší hodnoty K. V první fázi si čísla rozdělíme do přihrádek (skupin) podle nejméně významné cifry a spojíme do jedné posloupnosti, v druhé fázi čísla roztřídíme podle druhé nejméně významné cifry a opět spojíme do jedné posloupnosti, atd. Je důležité, aby se uvnitř každé přihrádky zachovalo pořadí čísel v posloupnosti na začátku fáze, tj. posloupnost uložená v každé přihrádce je vybranou podposloupností posloupnosti ze začátku fáze. Tvrdíme, že na konci i-té fáze obsahuje výsledná posloupnost čísla utříděná podle i nejméně významných cifer. Zřejmě i-té nejméně významné cifry tvoří rostoucí posloupnost, neboť podle nich jsme právě v této fázi rozdělovali čísla do přihrádek, a pokud dvě čísla mají tuto cifru stejnou, jsou uložena v pořadí dle jejich i-1 nejméně významných cifer, neboť v každé přihrádce jsme zachovali pořadí čísel z konce minulé fáze. Na závěr poznamenejme, že místo čísel podle cifer lze do přihrádek rozdělovat též textové řetězce podle jejich znaků, atp.

Časová složitost této varianty RadixSortu, pokud třídíme celá čísla od 1 do K a v každém kroku je rozdělujeme do l přihrádek, je O((N+l) logl K), tedy O(N), pokud K a l jsou konstanty. My si předvedeme implementaci algoritmu pro K=255 a l=2 (čísla budeme roztřiďovat podle bitů v jejich binárním zápisu).

    const K=255;
procedure RadixSort(var A: Pole);
  var P0,P1: Pole;
  k1,k2: integer;
  i: integer;
  bit: integer;

begin
  bit:=1;
  while bit<=K do
      begin
          k1:=0; k2:=0;
          for i:=1 to N do
          if (A[i] and bit)=0 then
              begin
                  k1:=k1+1; P0[k1]:=A[i];
              end;
          else
              begin
                  k2:=k2+1; P1[k2]:=A[i];
              end;
          for i:=1 to k1 do A[i]:=P0[i];
          for i:=1 to k2 do A[k1+i]:=P1[i];
          bit:=bit shl 1;
      end;
end;

 

 

 

 

Kontakt

Zdeněk Sovadina

zdeneksov@volny.cz

Osvobození 142
691 10 Kobylí

Vyhledávání

© SOZDA 2008 Všechna práva vyhrazena.

Vytvořte si webové stránky zdarma!Webnode