30.Prednaska
| 30. Prednáška |
Triedenie
Algoritmus triedenia má za úlohu vzostupne (alebo zostupne) usporiadať nejakú údajovú štruktúru podľa niektorých hodnôt. Pre jednoduchosť budeme vzostupne usporadovať postupnosť celých čísel. U všetkých triedení okrem triedenia zlučovaním (MergeSort) budeme triediť jednorozmerné N-prvkové celočíselné pole Pole a niekedy použijeme pomocnú procedúru Vymen. Spoločné deklarácie pre všetky triedenia:
var Pole: array [0..N - 1] of Integer; procedure Vymen(I, J: Integer); var T: Integer; begin T := Pole[I]; Pole[I] := Pole[J]; Pole[J] := T; end;
Pri rôznych algoritmoch triedení nás bude zaujímať ako efektívne tento pracuje. Pre malý počet prvkov asi nie je veľmi podstatné, či algoritmus bežal 5 alebo 6 milisekúnd, ale pre väčšie postupnosti hodnôt (napr. milión) už môže zavážiť, či triedenie pobeží 30 alebo 1 000 000 sekúnd. Vzhľadom na efektívnosť algoritmu sú dôležité informácie napr. o počte porovnávaní a počte výmen medzi prvkami.
Vizualizácia triedenia
Priebeh algoritmu triedenia sa dá rôzne vizualizovať, napr. [1], [2], [3] alebo [4].
My na testovanie rôznych triedení použijeme tento projekt, v ktorom zadefinujeme triedu TSort na vizualizáciu priebehu triedenia. Samotný triediaci algoritmus sa bude nachádzať v metóde Sort. Po zatlačení tlačidla Button1 sa vygeneruje náhodná postupnosť čísel, ktorú bude treba utriediť. Do algoritmu triedenia sme pridali aj zvyšovanie hodnoty premennej Pocet po každom porovnaní, aby sme lepšie videli "zložitosť" tohto algoritmu.
Potom samotný projekt vyzerá takto:
procedure TForm1.Button1Click(Sender: TObject);
var
Sort: TSort;
Pole: TPole;
I: Integer;
begin
Image1.Canvas.FillRect(Image1.ClientRect);
SetLength(Pole, Image1.Width div 2);
for I := 0 to High(Pole) do
Pole[I] := Random(Image1.Height - 15) + 10;
Sort := TSort.Create(Pole, Image1);
Sort.Sort;
Label2.Caption := 'počet porovnaní = ' + IntToStr(Sort.Pocet);
Sort.Free;
end;
A definícia triedy TSort:
type
TPole = array of Integer;
TSort = class
private
Image: TImage;
Vyska, Sirka: Integer;
FPole: TPole;
function DajN: Integer;
function DajPrvokPola(Index: Integer): Integer;
procedure PriradDoPola(Index, Hodnota: Integer);
procedure KresliPrvok(Index: Integer; Farba: TColor);
procedure Kresli(Farba: TColor);
procedure Vymen(Index1, Index2: Integer);
property Pole[Index: Integer]: Integer read DajPrvokPola write PriradDoPola;
property N: Integer read DajN;
public
Pocet: Integer; // počet porovnaní
constructor Create(const NovePole: TPole; NovyImage: TImage);
procedure Sort;
end;
{ TSort }
constructor TSort.Create(const NovePole: TPole; NovyImage: TImage);
begin
FPole := Copy(NovePole, 0, Length(NovePole));
Vyska := NovyImage.Height;
Sirka := NovyImage.Width div Length(NovePole);
Image := NovyImage;
Kresli(clBlue);
Pocet := 0;
end;
function TSort.DajPrvokPola(Index: Integer): Integer;
begin
Result := FPole[Index];
end;
function TSort.DajN: Integer;
begin
Result := Length(FPole);
end;
procedure TSort.KresliPrvok(Index: Integer; Farba: TColor);
begin
with Image.Canvas do
begin
Pen.Color := Farba;
MoveTo(Sirka * Index, Vyska);
LineTo(Sirka * Index, Vyska - FPole[Index] - 1);
end;
end;
procedure TSort.Vymen(Index1, Index2: Integer);
var
T: Integer;
begin
if Index1 = Index2 then
Exit;
// T := Pole[Index1]; Pole[Index1] := Pole[Index2]; Pole[Index2] := T;
KresliPrvok(Index1, clWhite);
KresliPrvok(Index2, clWhite);
T := FPole[Index1];
FPole[Index1] := FPole[Index2];
FPole[Index2] := T;
KresliPrvok(Index1, clBlue);
KresliPrvok(Index2, clBlue);
Image.Repaint;
end;
procedure TSort.PriradDoPola(Index, Hodnota: Integer);
begin
if FPole[Index] = Hodnota then
Exit;
KresliPrvok(Index, clWhite);
FPole[Index] := Hodnota;
KresliPrvok(Index, clBlue);
Image.Repaint;
end;
procedure TSort.Kresli(Farba: TColor);
var
I: Integer;
begin
for I := 0 to High(FPole) do
KresliPrvok(I, Farba);
Image.Repaint;
end;
// sem príde nejaký konkrétny algoritmus triedenia:
procedure TSort.Sort;
begin
// algoritmus triedi jednorozmerné pole Pole
// prvky poľa sa indexujú od 0 do N-1
// procedúra by mala zvýšovať o 1 obsah premennej Pocet (počítadlo porovnaní)
// pri každom porovnávaní hodnôt dvoch prvkov poľa
end;
Bublinkové triedenie (Bubble Sort)
Toto triedenie - hoci je asi najznámejšie (napr. wikipedia) - je z hľadiska efektívnosti skoro najhoršie, aké môže byť - môžeme ho použiť len pre malé polia v situácii, keď nezáleží na rýchlosti. Pracuje na princípe postupného porovnávania všetkých dvojíc susediacich prvkov: do prvku poľa s menším indexom ide menší z nich. Po jednom prechode celým poľom sa maximálny prvok určite dostane na koniec poľa. Potom ostáva utriediť N-1 prvkov poľa (posledný je už na svojom mieste):
procedure TSort.Sort;
var
I, J: Integer;
begin
for I := N - 2 downto 0 do
for J := 0 to I do
begin
if Pole[J] > Pole[J + 1] then
Vymen(J, J + 1);
Inc(Pocet);
end;
end;
Poznámky:
- počet porovnaní je vždy N*(N-1)/2 (aj keby bolo pole už dopredu utriedené)
- počet výmen je v "najhoršom prípade" N*(N-1)/2
- algoritmus sa dá trochu "vylepšiť": vonkajší for-cyklus sa nahradí repeat-cyklom s takou podmienkou ukončenia, ktorá skončí cyklus, ak vnútorný for-cyklus nespravil ani jednu výmenu
Min Sort
V literatúre sa niekedy dá nájsť aj názov Selection Sort.
Nájde v úseku poľa minimálny prvok, vymení ho s prvým prvkom úseku a posunie dolnú hranicu triedeného úseku o 1 (t.j. triedený úsek poľa sa skráti o 1), atď.
procedure TSort.Sort;
var
I, J, Min: Integer;
begin
for I := 0 to N - 2 do
begin
Min := I;
for J := I + 1 to N - 1 do
begin
if Pole[J] < Pole[Min] then
Min := J;
Inc(Pocet);
end;
Vymen(I, Min);
end;
end;
Poznámky:
- porovnaní je rovnako ako pri triedení BubbleSort, ale výrazne menej výmen (maximálne N-1)
- toto triedenie môžeme použiť vtedy, keď porovnanie dvoch prvkov poľa je rýchle a pomalú výmenu dvoch prvkov potrebujeme urobiť podľa možnosti čo najmenejkrát
- naprogramujte analogicky fungujúci "Max Sort" (v každom prechode cyklu nájde maximálny prvok a vymení ho s prvkom na začiatku poľa)
Triedenie vsúvaním (Insert Sort)
Predpokladajme, že istá časť poľa je už utriedená. Počas tohto triedenia sa ďalší (ešte neutriedený) prvok zaradí na svoje miesto a tým sa predĺži utriedený úsek o 1. Takéto triedenie nazývame triedenie vsúvaním, t.j. InsertSort (pozri napr. wikipediu).Opäť je to veľmi pomalý algoritmus - porovnateľný s Bubble Sortom.
Námety:
- naprogramujte triedenie vsúvaním: prechádzame už utriedenú časť poľa od konca a všetky väčšie prvky posúvame vpravo, tým sa vyrobí voľné miesto pre vsúvaný prvok
- algoritmus by sa dal urýchliť, ak by sme miesto na vsunutie nového prvku hľadali binárnym vyhľadávaním a zároveň by sme dokázali čo najrýchlejšie rozsunúť prvky poľa (napr. štandardnou procedúrou Move)
Triedenie zlučovaním (Merge Sort)
Vychádza z metódy rozdeľuj a panuj, t.j. ľahšie sa utriedi menej položiek ako veľa. Tento algoritmus môžeme popísať takto (pozri napr. wikipediu):
- pole najprv rozdelíme na dve približne rovnako veľké časti (pri nepárnom počte je jedna časť o 1 väčšia),
- ďalej sa budeme zaoberať každou z týchto dvoch častí zvlášť a to takým istým spôsobom, t.j. rozdelíme ich na dve časti,
- znovu vezmeme prvú z nich a rozdelíme ju na dve, atď. ... až kým nedostaneme jednoprvkové úseky,
- je zrejmé, že jednoprvkové úseky sú vždy utriedené,
- teraz použijeme druhú časť algoritmu: zlúčenie dvoch utriedených častí tak, aby aj novovzniknutá časť bola utriedená, t.j. dostávame časť s dvoma položkami,
- podobne sa rozdelí a zlúči aj druhá časť z rozdelenia a dostávame utriedenú druhú dvojprvkovú časť,
- ten istý algoritmus zlúčenia dvoch utriedených častí použijeme aj teraz a dostávame utriedenú štvorprvkovú časť ...
- algoritmus sa bude opakovať, až kým nebude utriedené celé pole.
Toto triedenie sa používa najmä pri triedení prvkov spájaných zoznamov - zlučovanie dvoch polí bez pomocného poľa je veľmi náročná operácia a môže pokaziť efektívnosť celého algoritmu. Toto triedenie patrí medzi tzv. rýchle triedenia - "efektívnosť" je rádovo N*log2 N.
Námety:
- usporiadať prvky spájaného zoznamu
- usporiadať v poli pomocou pomocného poľa
- usporiadať v poli bez pomocného poľa (asi bude priveľa posunov poľa)
- triediť binárny súbor s dvoma pomocnými súbormi
- triediť zoznam (alebo pole) bez rekurzie
Rýchle triedenie (Quick Sort)
Je to najznámejší algoritmus triedenia, ktorý v roku 1960 vymyslel Hoare (pozri napr. wikipediu). V predchádzajúcom triedení sme museli dva už utriedené zoznamy zlúčiť tak, aby aj výsledok bol utriedený. Triedenie QuickSort na rozdiel od MergeSortu, vytvorí dve samostatné časti poľa tak, aby ich už nebolo treba nejako špeciálne zlučovať, ale aby ich stačilo iba položiť za seba:
- v prvom kroku sa jeden prvok vyberie za tzv. pivota (v princípe to môže byť ľubovoľný prvok, my vyberieme prvý prvok z danej postupnosti)
- podľa tohto pivota rozdelíme vstupnú postupnosť prvkov na dve časti: v prvej z nich budú len čísla menšie ako pivot a v druhej zase len čísla väčšie a rovné ako pivot (ideálne by bolo, keby sa postupnosť rozdelila na dve približne rovnako veľké časti, v najhoršom prípade to môže dopadnúť tak, že v jednej časti je nula prvkov a v druhej sú všetky ostatné prvky)
- po takomto rozdelení postupnosti dostávame tri časti - časť s jediným prvkom, ktorým je pivot; časť, v ktorej sú prvky menšie ako pivot; a časť s prvkami väčšími alebo rovnými ako je pivot
- potom rovnakým spôsobom utriedime druhú časť (prvky menšie ako pivot) a tretiu časť (prvky väčšie alebo rovné ako pivot)
- po ich utriedení druhú a tretiu časť "položíme" vedľa seba, pričom pivot dáme na správne miesto
Rýchle triedenie - QuickSort:
procedure TSort.Sort;
procedure Rozdel(Z, K: Integer; var Ip: Integer);
var
Pivot: Integer;
I: Integer;
begin
Pivot := Pole[Z]; // pivot je prvý prvok
Ip := Z;
for I := Z + 1 to K do // prejdi všetky prvky medzi Z+1 a K
begin
if Pole[I] < Pivot then // I-ty prvok patrí do prvej časti poľa
begin // teraz je o jeden viac takých, čo sú menšie ako Pivot
Inc(Ip);
Vymen(Ip, I);
end;
Inc(Pocet);
end;
Vymen(Z, Ip); // daj Pivot na správne miesto
// v Ip je teraz index, na ktorom je umiestnený pivot
end;
procedure Quick(Z, K: Integer);
var
IPivot: Integer; // index, kde je Pivot
begin
if Z >= K then
Exit;
Rozdel(Z, K, IPivot);
Quick(Z, IPivot - 1);
Quick(IPivot + 1, K);
end;
begin
Quick(0, N - 1);
end;
Poznámky:
- procedúra Quick je rekurzívna a triedi časť poľa medzi indexmi Z a K, pričom najprv volá procedúru Rozdel na rozdelenie tejto časti a zistenie indexu pivota, potom aplikuje ten istý algoritmus na časť poľa pred indexom, na ktorom je pivot a na časť poľa za pivotom
- procedúra Rozdel dáva prvky menšie ako pivot na začiatok poľa, prvky väčšie alebo rovné ako pivot na koniec poľa a po skončení tohto upratovania dá ešte pivot na správne miesto (medzi tieto dve časti) a vráti jeho index v parametri Ip
- ak bolo pole už utriedené ešte pred samotným triedením, tak je zvolený najhorší možný pivot, preto sa na začiatku procedúry Rozdel zvykne pridať:
Vymen(Z, (Z + K) div 2);
Ďalšie námety:
- v praxi sa väčšinou používa bez rekurzie - preprogramujte toto triedenie bez rekurzie
- triediť spájaný zoznam
- triediť binárny súbor
- prerobte procedúru Rozdel na funkciu s dvoma parametrami Z a K, ktorá vráti index pivota
Radix Sort
Mohli by sme si ho predstaviť ako triedenie po cifrách (pozri napr. wikipediu):
- pripravíme K pomocných kôpok, do ktorých budeme prehadzovať hodnoty zo vstupnej postupnosti
- nech K je počet rôznych hodnôt, ktoré môžu nadobúdať jednotlivé cifry (napr. pre čísla 10, pre znaky 26 a pod.)
- v prvom prechode postupne prehadzujeme všetky hodnoty do príslušnej kôpky podľa poslednej cifry
- potom všetky kôpky spojíme a tým vytvoríme opäť jednu postupnosť
- v druhom prechode prehadzujeme hodnoty do kôpok podľa predposlednej cifry
- opäť ich potom spojíme do jednej postupnosti
- toto postupne opakujeme pre všetky cifry - na záver je celá postupnosť utriedená vzostupne
Takto sa dobre triedia spájané zoznamy. Pri práci s poliami si tento algoritmus vyžaduje veľa pomocných polí.
Ďalšie námety:
- naprogramujte toto triedenie pre spájané zoznamy, pole, binárny súbor
