Triedenia

Triedenia

30. mar.1999

Bublinkové triedenie (BubbleSort)

najhoršie aké môže byť
porovnávanie dvoch prvkov vedľa seba a do menšieho indexu poľa ide menší z nich
po jednom prechode poľom sa určite maximálny prvok dostane na koniec poľa, potom ostáva utriediť N-1 prvkov poľa (posledný je už na svojom mieste)

for i:=n downto 2 do
for j:=1 to i-1 do { prebublávanie úseku 1..i }
    if a[j]>a[j+1] then
      begin
        p:=a[j]; a[j]:=a[j+1]; a[j+1]:=p   {výmena, lebo v menšom indexe väčší prvok}
      end;

počet výmen n*(n-1)/2

MaxSort

nájdi v úseku maximálny prvok, vymeň ho s posledným prvkom, skráť triedené pole o 1, atď.

for i:=n downto 2 do
begin
    m:=1;
    for j:=2 to i do
      if a[j]>a[m] then m:=j;
    if i<>m then
      begin
        x:=a[m]; a[m]:=a[i]; a[i]:=x;
      end
end;

porovnaní je rovnako ako BubbleSort, ale menej výmen

Triedenie vsúvaním (InsertSort)

istá časť poľa je utriedená, zaraď nový prvok na svoje miesto

for i:=2 to n do
begin { predpoklad: 1..i-1 je utriedený úsek, vsuň a[i] tak, aby ostal utriedený }
    j:=i-1; t:=a[i];
    while (j>0) and (a[j]>t) do
      begin { hľadanie vhodného miesta pre prvok a[i] }
        a[j+1]:=a[j]; dec(j)
      end;
    a[j+1]:=t;
end;

použi len v krajných prípadoch

NDÚ: nájdite vhodné miesta v algoritmoch tak, aby sa triedenia zobrazovali

Príklad

Je daný binárny súbor student.dat, ktorého vety sú tejto štruktúry student=record
meno,priez:string[20];
nar:datum
end; Napíšte program, ktorý načíta daný súbor do nejakej dátovej štruktúry a potom utriedi túto tabuľku vzostupne podľa priezvisk, ak sú rovnaké, podľa mien a ak sú aj tie rovnaké, v utriedenej tabuľke bude najprv človek, ktorý je starší. Vypíšte utriedenú tabuľku.

const max=100;

type datum=record den,mes,rok:integer end;
     student=record
       meno,priez:string[20];
       nar:datum
     end;

tstudent=record p:integer; s:array[1..max] of student end;

procedure citaj(var t:tstudent);
var f:file of student;
begin
assign(f,'student.dat'); reset(f);
with t do
    begin
      p:=0;
      while not eof(f) do
        begin
          inc(p);
          read(f,s[p]);
        end
    end
end;

procedure vypis(var t:tstudent);
var i:integer;
begin
with t do
    for i:=1 to p do
      with s[i],nar do
        writeln(priez,' ',meno,' ',den,'. ',mes,'. ',rok);
end;

function mensidat(x,y:datum):boolean;
begin
if x.rok=y.rok then
if x.mes=y.mes then mensidat:=x.den<y.den
else mensidat:=x.mes<y.mes
else mensidat:=x.rok<y.rok
end;

function mensi(a,b:student):boolean;
begin
if a.priez=b.priez then
if a.meno=b.meno then mensi:=mensidat(a.nar,b.nar)
else mensi:=a.meno<b.meno
else mensi:=a.priez<b.priez
end;

procedure tried(var t:tstudent); { minsort }
var i,j,imin:integer;
    pom:student;
begin
for i:=1 to t.p-1 do
    begin
      imin:=i;
      for j:=i+1 to t.p do
        if mensi(t.s[j],t.s[imin]) then imin:=j;
      if imin<>i then
        begin
          pom:=t.s[i];
          t.s[i]:=t.s[imin];
          t.s[imin]:=pom;
        end
    end
end;

var t:tstudent;

begin { hlavný program }
citaj(t);
writeln('======== tabulka ===========');
vypis(t);
writeln('======== a utriedena ===========');
tried(t);
vypis(t);
readln;
end.

Triedenie zlučovaním (MergeSort)

metóda rozdeľuj a panuj, t.j. ľahšie sa utriedi menej položiek ako veľa
algoritmus

pole rozdelíme na dve približne rovnako veľké časti (pri nepárnom počte je jedna časť väčšia)
potom sa zaoberajme s každou z týchto dvoch častí zvlášť a to takým istým spôsobom, t.j. rozdelíme ju na dve čast
znovu vezmime prvú z nich a rozdeľme ju na dve, atď. ... až kým nedostaneme jednoprvkové úseky
je zrejmé, že jedna položka je utriedená a teda máme dve utriedené časti
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

hlavný program:

const n=100;
type zoznam=^vrchol;
     vrchol=record h:integer; next:zoznam end;
var p,pom:zoznam;
    i,j:integer;
begin
writeln('*** merge sort');
randomize; p:=nil;
for i:=1 to n do { vytvorenie jednosmerného spájaného zoznamu
                    dĺžky N s náhodnými hodnotami, pridávaním na začiatok}
    begin
      new(pom);
      pom^.h:=random(100)+1; pom^.next:=p; p:=pom
    end;
vypis(p);
mergesort(p);
vypis(p);
end.

procedúra mergesort spracuje celý zoznam tak, že ho rozdelí na dve časti s približne rovnakým počtom prvkov, na tieto zavolá tú istú procedúru (pokiaľ sú zoznamy viac ako jednoprvkové) a potom takto vzniknuté zoznamy zlúči

procedure mergesort(var p:zoznam);
var druhapol:zoznam;
begin
if (p<>nil) and (p^.next<>nil) then { aspoň 2 prvky }
    begin
      rozdel(p,druhapol);
      mergesort(p);
      mergesort(druhapol);
      zluc(p,druhapol,p)
    end;
end;

procedúra rozdel sa bude snažiť nájsť "polovicu" celého zoznamu, ktorý dostáva cez smerník p a vráti dva zoznamy s približne rovnakým počtom prvkov, stred sa bude hľadať tak, že po zozname budú "putovať" dva smerníky, jeden po jednom kroku a druhý po dvoch, a ak sa druhý smerník prepracuje na koniec zoznamu, zrejme prvý, ktorý šiel po kroku, bude práve v polovici zoznamu

procedure rozdel(var p,dp:zoznam);
var stred,pom:zoznam;
begin
stred:=p;
if stred=nil then dp:=nil       {nebolo čo deliť }
else
    begin
      pom:=stred^.next;
      while pom<>nil do           {pokiaľ nie je na konci zoznamu }
        begin
          pom:=pom^.next;         {posuň sa o jeden krok }
          if pom<>nil then        {ešte nie som na konci}
            begin
              stred:=stred^.next; {posuň stred o jeden krok }
              pom:=pom^.next;     {posuň sa o druhý krok}
            end;
        end;
      dp:=stred^.next; { vráť smerník na prvok, ktorý je stredný }
      stred^.next:=nil; { zmodifikuj pôvodný dlhý zoznam na polovičný }
    end;
end;

ak máme dobre rozdelený zoznam na dve časti a vraciame sa z rekurzie ostáva nám iba dobre tieto dve časti zlúčiť a to tak, aby aj nový, dlhší zoznam, ostal utriedený; procedúra zluc teda prechádza oboma zoznamami a vytvára z nich nový

procedure zluc(p1,p2:zoznam; var p:zoznam);
var posl:zoznam;
begin
if p1=nil then p:=p2       {ak je zoznam p1 prázdny }
else if p2=nil then p:=p1 { ak je zoznamp2prázdny }
else                       {oba zoznamy sú neprázdne }
    begin
      if p1^.h <= p2^.h then { vyriešme prvý prvok nového zoznamu }
        begin
          p:=p1; p1:=p1^.next;
        end
      else
        begin
          p:=p2; p2:=p2^.next;
        end;
      posl:=p; { vytvárajme zoznamppridávaním na koniec pomocou pomoc. smerníka posl }
      while (p1<>nil) and (p2<>nil) do {pokiaľ sa neminie aspoň jeden zo zoznamov }
                {pridávame do nového zoznamu tak, aby ostal utriedený }
        if p1^.h <= p2^.h then
          begin
            posl^.next:=p1; posl:=p1; p1:=p1^.next;
          end
        else
          begin
            posl^.next:=p2; posl:=p2; p2:=p2^.next;
          end;
      if p1=nil then posl^.next:=p2 {vyprázdnil sa zoznam p1 }
      else posl^.next:=p1           {vyprázdnil sa zoznam p2 }
    end;
end; NDÚ:

usporiadať v poli pomocou pomocného poľa veľkosti n (resp. n/2)
usporiadať v poli bez pomocného poľa (priveľa posunov poľa)
triediť binárny súbor s dvoma pomocnými
triediť zoznam, pole bez rekurzie

Rýchle triedenie (QuickSort)

v predchádzajúcom triedení sme museli zoznamy dobre zlúčiť
toto triedenie vytvára zoznamy tak, aby už boli dobré a aby stačilo iba ich položiť za seba a aby sa ich utriedenosť týmto nepokazila:

v prvom kroku sa jeden prvok vyberie za PIVOTa (v princípe to môže byť ľubovoľný prvok, my vyberme prvý prvok z danej postupnosti)
podľa tohto pivota rozdeľme vstupnú postupnosť prvkov na dve časti, pričom v prvej z nich budú čísla menšie ako pivot a v druhej čísla väčšie a rovné ako pivot (v najlepšom z prípadov sa postupnosť rozdelí na dve časti, s približne rovnakým počtom prvkov, v najhoršom prípade však zrejme na nula prvokov, ktoré bude tvoriť prvú časť a na 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 ako pivot)
po ich utriedení druhú a tretiu časť "položíme" vedľa seba, pričom pivot dáme na správne miesto

program:

const n=100;
type pole=array[1..n] of integer;
var p:pole;
i:integer;
begin
writeln('*** quick sort');
randomize;
for i:=1 to n do p[i]:=random(100)+1; { náhodne vygeneruj pole }
for i:=1 to n do write(p[i],' '); writeln;
quicksort(1,n); {utrieď pomocou quicksortu celé pole }
for i:=1 to n do write(p[i],' '); writeln;
end.

procedúra quicksort je rekurzívna a triedi časť poľa medzi indexami z a k, pričom najprv volá procedúru rozdel na rozdelenie tejto časti a zistenie indexu pivota, potom aplikuje ten istý algoritmus na čast poľa pred indexom, na ktorom je pivot a na časť poľa za pivotom

procedure quicksort(z,k:integer);
var ipivot:integer;
begin
if z<k then { aspoň 2 prvky }
    begin
      rozdel(z,k,ipivot);
      quicksort(z,ipivot-1);
      quicksort(ipivot+1,k);
    end;
end;

ostáva ešte napísať procedúru rozdel, ktorá zrejme 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 a vráti jeho index

procedure rozdel(z,k:integer; var ip:integer);
var pivot:integer;
    i,pmin:integer;
begin
pivot:=p[z]; pmin:=z;   { pivot je prvý prvok}
for i:=z+1 to k do      { prejdi všetky prvky medzi z+1 a k }
    if p[i]<pivot then    { pozeraný prvok patrí do prvej časti poľa }
      begin
                          {je o jeden viac takých, čo sú menšie ako pivot }
        inc(pmin); vymen(pmin,i);
      end;
vymen(z,pmin);          {daj pivot na správne miesto }
ip:=pmin                {vráť index, na ktorom je umiestnený pivot }
end;

pomocná procedúra vymen vymieňa hodnoty prvkov s danými indexami

procedure vymen(i,j:integer);
var x:integer;
begin x:=p[i]; p[i]:=p[j]; p[j]:=x; inc(pv); end;

ak je utriedené pole, tak je zvolený najhorší možný pivot, preto sa na zač. rozdel pridá:

vymen(z,(z+k)div 2); NDÚ:

triediť pole bez rekurzie
triediť spájaný zoznam
triediť binárny súbor

Triedenie haldou (HeapSort)

triedenie poľa haldou
halda: ak je otec na indexe I, synovia na miestach s indexami 2*I a 2*I+1, pričom platí, že otec má väčšiu hodnotu ako hociktorý zo synov a oba podstromy sú opäť haldy (pre jednoduchosť predpokladáme, že všetky prvky poľa sú rôzne)
dve fázy

vytvorenie haldy
v halde je koreň, t.j. prvý prvok najväčší prvok zo všetkých, jeho výmena s posledným prvkom ešte neutriedeného poľa a nové "uhaldovanie"

const n=100;
var a:array[1..n] of integer;
i,j,m,t,p,pp:integer;
begin
writeln('*** heap sort');
randomize;
for i:=1 to n do a[i]:=random(100)+1;
for i:=1 to n do write(a[i],' '); writeln;
heapsort(n);
for i:=1 to n do write(a[i],' '); writeln;
end.

procedure heapsort(n:integer);
begin
vytvor_haldu(n);
i:=n;                  {ber postupne všetky prvky }
while i>1 do
    begin                {vymen 1. a posledný zatiaľ neutriedený, t.j. i-ty prvok }
      t:=a[1]; a[1]:=a[i]; a[i]:=t;
      dec(i);            {zmenši rozmer stromu }
      uprac_haldu(1,i); { oprav strom - koreň je asi zlý }
    end;
end;

procedúra uprac_haldu vytvára haldu v poli medzi zadanými dvoma indexami poľa, t.j. po jej skončení je časť poľa K až M haldou, pričom procedúra predpokladá, že časť K+1 až M je halda, ale tým, že sme pridali prvok na miesto K, mohla sa halda K až M pokaziť a preto treba pole znovu "uhaldovať", t.j. zabezpečiť, aby aj pre otca K platilo, že má oboch synov menších ako on sám (ak to tak nie je, treba ho zrejme vymeniť s väčším zo synov a postup opakovať pre tohto syna a príslušný podstrom)

procedure uprac_haldu(k,m:integer);
   { predpokladáme, že od k+1 domto už halda je - pridáme k-ty }
var i,t:integer;
begin
t:=a[k]; i:=k; posun(i,m);
while a[k]<a[i] do
    begin
      a[k]:=a[i]; k:=i; a[k]:=t;
      posun(i,m); { vije nový väčší syn }
    end;
end;

procedure vytvor_haldu(n:integer);
var i:integer;
begin
for i:= n div 2 downto 2 do uprac_haldu(i,n)
end;

pomocná procedúra posun posúva prvý parameter na väčšieho syna

procedure posun(var i:integer; m:integer);
   { ak existuje syn -> nastaví sa na väčšieho z nich }
begin
if i<=m div 2 then { aspoň jeden syn existuje}
    begin
      i:=2*i; { v i je ľavý syn }
      if (i<m) and (a[i+1]>a[i]) then i:=i+1
          { pravý syn bol väčší a preto je v i pravý syn inak ostáva v i ľavý syn }
    end;
end; NDÚ:

triedenie indexov poľa pre všetky možné triedenia