╪azenφ dat - algoritmy a °adφcφ metody
21. prosince 1998   skrivan@fi.muni.cz


╪azenφ dat pat°φ k nejΦast∞jÜφm programßtorsk²m ·kol∙m. Se°adit data pot°ebujeme vÜude tam, kde je nutnΘ ze zm∞ti ·daj∙ zadan²ch postupn∞ u₧ivatelem zφskat n∞jak² p°ehledn² v²sledek, nap°. seznam set°φd∞n² podle abecedy. ╪adφcφch metod je velkß spousta, uvedu zde ty nejb∞₧n∞jÜφ, teoretick² v²klad je dopln∞n praktick²mi ukßzkami v jazyce Pascal.

Obsah

  1. Zßkladnφ pojmy
  2. Metoda p°φmΘho v²b∞ru
  3. Metoda p°φmΘho vklßdßnφ
  4. Quick Sort
  5. Bubble Sort

1. Zßkladnφ pojmy

╪adφcφ metoda
Je obecn∞ postup, jeho₧ provedenφm zφskßme set°φd∞n² v²sledek podle danΘho kritΘria. Ka₧dß °adφcφ metoda mß sv∙j odliÜn² postup, jak²m dß set°φd∞nß data na v²stup.
P°irozenost metody
╪adφcφ metoda se naz²vß p°irozenß, jestli₧e doba pot°ebnß k se°azenφ ji₧ se°azenΘ podmno₧iny ·daj∙ je menÜφ, ne₧ doba pot°ebnß na se°azenφ zb²vajφcφ neuspo°ßdanΘ podmno₧iny. Pokud tato podmφnka nenφ spln∞na, pak se metoda oznaΦuje za nep°irozenou.
Stabilita algoritmu
Algoritmus je stabilnφ, jestli₧e zachovßvß stejnΘ po°adφ zßznam∙ se stejn²m klφΦem. Tato vlastnost je po₧adovßna v t∞ch p°φpadech, ve kter²ch skupiny zßznam∙ se stejnou hodnotou klφΦovΘ polo₧ky jeÜt∞ uvnit° °adφme podle jinΘho klφΦe.
Rychlost algoritmu
N∞kdy takΘ naz²vßna algoritmickß slo₧itost, lze chßpat jako poΦet provedenφ porovnßnφ klφΦov²ch polo₧ek, kterß jsou nutnß pro zφskßnφ uspo°ßdanφ posloupnosti. Algoritmickß slo₧itost pro N zßznam∙ je: U₧ snad jenom pro up°esn∞nφ, Φasov∞ nejv²hodn∞jÜφ je slo₧itost logaritmickß, nejhorÜφ p°φpad je slo₧itost faktorißlnφ a jφ podobnΘ.


2. Metoda p°φmΘho v²b∞ru

P°edpoklßdejme, ₧e Φßst pole od indexu 1 a₧ po K je se°azenß a Φßst od K+1 do N nese°azenß. V posloupnosti od K+1 do N nalezneme minimßlnφ prvek (nech¥ je nalezen na pozici M). Potom tedy prohodφme M-t² prvek s K+1nφm prvkem a za se°azenou pova₧ujeme posloupnost od 1 do K+1. Na zaΦßtku je uspo°ßdanß posloupnost prßzdnß, tj. hledßme minimum z prvk∙ od 1 do K+1 a nalezen² prvek prohodφme s 1. polo₧kou.
Metoda nepat°φ mezi stabilnφ, a ani nenφ ₧ßdn²m rychlφkem.

 var i, j, k: index;
     x, pom: prvek;
     a: array [index] of prvek;

 begin
       for j:=1 to n do
        begin
             x:=a[j];
             k:=j;
             for i:=j+1 to n do
              if x<a[i] then begin x:=a[i]; k:=i; end;
             pom:=a[i];
             a[i]:=a[k];
             a[k]:=pom;
             inc(j);
        end;
 end.


3. Metoda p°φmΘho vklßdßnφ

P°edpoklßdejme, ₧e Φßst pole od indexu 1 a₧ po K je set°φd∞nß. Vezmeme K+1 prvek a vlo₧φme jej na sprßvnΘ mφsto do ji₧ uspo°ßdanΘ posloupnosti a za se°azenou pova₧ujeme posloupnost od 1 do K+1. Na zaΦßtku pova₧ujeme za uspo°ßdanou posloupnost pouze prvek 1.
Metoda se chovß p°irozen∞ a je stabilnφ. AvÜak mezi rychlΘ metody zrovna nepat°φ.

 var i, j: index;
     x: prvek;
     a: array [index] of prvek;

 begin
 	for i:=2 to n do
         begin
              x:=a[i];
              a[0]:=x;
              j:=i-1;
              while x<a[j] do
               begin
                    a[j+1]:=a[j];
                    dec(j);
               end;
              a[j+1]:=x;
         end;
 end.


4. Quick Sort

Metoda Quick Sort je zalo₧enß na rekurzi. Vyu₧φvß principu d∞lenφ °azenΘho pole. ╪azenΘ pole rozd∞lφme na dv∞ Φßsti A a B, pro kterΘ bude platit, ₧e vÜechny prvky z A jsou menÜφ ne₧ libovoln² prvek z B. Toto provßdφme rekurzivn∞ tak dlouho, dokud celΘ pole nenφ se°azenΘ. ╚ßst algoritmu, kterß provßdφ rozd∞lovßnφ pole na Φßsti A a B, m∙₧e pracovat nap°. tak, ₧e hledß zleva nejbli₧Üφ dalÜφ prvek, kter² je v∞tÜφ nebo roven d∞lφcφ hodnot∞ x, a hledß zprava nejbli₧Üφ dalÜφ prvek, kter² je menÜφ nebo roven d∞lφcφ hodnot∞ x. Tyto prvky se vzßjemn∞ vym∞≥ujφ. V tΘto Φinnosti se pokraΦuje tak dlouho, dokud proti sob∞ postupujφcφ indexy, pomocφ kter²ch se prochßzφ °azenß Φßst pole, nep°ek°φ₧φ. Hodnota x se obvykle volφ jako prost°ednφ prvek. (tzv. medißn)
Metoda nenφ stabilnφ a nepracuje p°irozen∞. Je vÜak jednou z nejrychlejÜφch °adφcφch metod, i kdy₧ m∙₧e b²t n∞kdy na obtφ₧ p°φtomnß rekurze.

 var a: array [index] of prvek;
     n: index;

 procedure rozdel(l: index; var i,j: index; r: index);
 var w: prvek;
 begin
      i:=l;
      j:=r;
      x:=a[(l+r) div 2];
      repeat
      	    while a[i]<x do inc(i);
            while x<a[j] do dec(j);
            if i<=j then
             begin
             	   w:=a[i];
                   a[i]:=a[j];
                   a[j]:=w;
                   inc(i);
                   dec(j);
             end;
      until i>j;
 end;

 procedure trid(l,r: index);
 var i,j: index;
 begin
      rozdel(l,i,j,r);
      if l<j then trid(l,j);
      if i<r then trid(i,r);
 end;

 BEGIN
      trid(1,n);
 END.


5. Bubble Sort

BublinkovΘ t°φd∞nφ je v principu podobnΘ jako metoda p°φmΘho v²b∞ru, rozdφl je ve vyhledßvßnφ minima a jeho zßm∞na s prvnφm prvkem nese°azenΘ podposloupnosti. Nese°azenß Φßst pole se prochßzφ zprava doleva a porovnßvajφ se postupn∞ ka₧dΘ dva sousednφ prvky pole - nejsou-li vzßjemn∞ se°azeny ve smysly v²slednΘho °azenφ, vym∞nφ se.
Co se t²Φe rychlosti, jde snad o nejhorÜφ °adφcφ metodu. Vhodnß je jenom k otestovßnφ, zda danß posloupnost je uspo°ßdanß, nebo¥ v takovΘm p°φpad∞ metoda projde posloupnostφ pouze jednou. 

 var i,j: index;
     x: prvek;
     a: array [index] of prvek;

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


W3C
[Zp∞t] [Zm∞na k≤dovßnφ] [StromeΦek]
Zp∞t k≤dovßnφ stromeΦek