Razeni dat

Ř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 vude tam, kde je nutné ze změti údajů zadaných postupně uivatelem 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

Základní pojmy
Metoda přímého výběru
Metoda přímého vkládání
Quick Sort
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. Kadá řadící metoda má svůj odliný postup, jakým dá setříděná data na výstup.

Přirozenost metody

Řadící metoda se nazývá přirozená, jestlie doba potřebná k seřazení ji seřazené podmnoiny údajů je mení, ne doba potřebná na seřazení zbývající neuspořádané podmnoiny. Pokud tato podmínka není splněna, pak se metoda označuje za nepřirozenou.

Stabilita algoritmu

Algoritmus je stabilní, jestlie zachovává stejné pořadí záznamů se stejným klíčem. Tato vlastnost je poadována v těch případech, ve kterých skupiny záznamů se stejnou hodnotou klíčové poloky jetě uvnitř řadíme podle jiného klíče.

Rychlost algoritmu

Někdy také nazývána algoritmická sloitost, lze chápat jako počet provedení porovnání klíčových poloek, která jsou nutná pro získání uspořádaní posloupnosti. Algoritmická sloitost pro N záznamů je:

logaritmická O(log N)
lineární O(N)
polynomiální O(P(N)) (např. kvadratická O(n²), nebo kubická O(n³) )
exponenciální O(2^N)
faktoriální O(N!), nebo O(N^N)

U snad jenom pro upřesnění, časově nejvýhodnějí je sloitost logaritmická, nejhorí případ je sloitost 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 povaujeme 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. polokou.
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 povaujeme posloupnost od 1 do K+1. Na začátku povaujeme za uspořádanou posloupnost pouze prvek 1.
Metoda se chová přirozeně a je stabilní. Avak 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 zaloená 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 vechny 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 vak 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ě kadé 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.

[Zpět]	[Změna kódování]	[Stromeček]