Řazení údajů
------------

Řazení = uspořádání údajů podle velikosti
(existuje relace úplného uspořádání na množině dat)

[Třídění = rozdělení množiny dat na části (rozklad množiny)]

Přímé metody = realizace základního principu;
Modifikované metody = "zlepšení" principu

in situ = prostorová složitost je dána vstupními daty

stabilita metody = data se stejnými klíči se nepřeskupují

přímé řazení / nepřímé řazení = přeskupují / nepřeskupují se řazené 
údaje.

Metody:
- výběrové
- vkládací
- rozdělovací
- slučovací

Charakter metod:
- přirozené: jsou schopny využít částečně seřazených dat
- podle časové složitosti lineární, složené logaritmické, kvadratické, horší

Předpoklad: Pole P, obsazeno prvních N indexů, data jsou 
porovnatelná

Výběrové metody:
----------------

Přímý výběr (Straight Selection)
--------------------------------
procedure Zamena(var P:Pole; A,B: Indexy);
 var Pom: Slozka;
 begin Pom:=P[A];
       P[A]:=P[B];
       P[B]:=Pom
 end;

function Extrem(P:Pole;A,B:indexy):Indexy;
 var V,I:Indexy;
 begin V:=A;
       for I:=A+1 to B do
         if P[I]<P[V] then V:=I;
       Extrem:=V
 end;

for I:=N downto 2 do 
   Zamena(P, Extrem(P,1,I), I); 

časová složitost kvadratická (k.N2)

Bublinové řazení (Bubble Sort)
------------------------------
J:=1;
Jeste:=true;
while Jeste do begin
  Jeste:=false;
  for I:=1 to N-J do
     if P[I]>P[I+1] then begin
        Zamena(P, I, I+1);
        Jeste:=true
     end;
  inc(J)
end;

Přirozená, sekvenční, stabilní, implementační jednoduchost,
časová složitost kvadratická.

Řazení hromadou (Heap Sort)
---------------------------


procedure Sift(L,R:Index);
 var I,J: Index; Pom:Prvek; Jeste:Boolean; 
begin I:=L;
      J:=I*2;
      Pom:=P[I];
      Jeste:=J<=R;
      while Jeste do begin
        if J<R then 
           if P[J]<P[J+1] then J:=J+1;
        if P[I]<P[J] then begin
           P[I]:=P[J];
           I:=J;
           J:=I*2;
           Jeste:=J<=R
        end else Jeste:=false;
        P[I]:=Pom;
      end;
end;


for I:=N div 2 downto 1 do Sift(I, N);

for I:=N downto 2 do begin
   Zamena(P, 1, I);
   Sift(1, I-1)
end;

Nepřirozená, nestabilní, in-situ, časová složitost nejlepší = k.N.lb N
========================================

Vkládací metody
---------------
Přímé vkládání (straight insert)
--------------------------------
a) nalezení vhodného místa pro vkládaný prvek
b) odsun následných prvků
c) vložení nového prvku

in-situ, nesekvenční, stabilní varianta, časová složitost k.N2

Řazení bin. stromem
-------------------
vkládání nových prvků do stromové struktury v uspořádání
o<=ls
o>ps
inorder

procedure Vloz(var S:UkUzel; D:Prvek);
 begin if S=nil then begin
          new(S);
          S^.Data:=D;
          S^.Vlevo:=nil;
          S^.vpravo:=nil
        end else
          if D<S^.Data then Vloz(S^.Vlevo,D)
                       else Vloz(S^.Vpravo,D)
 end;

for I:=1 to N do begin
   read(X);
   Vloz(S, X)
end;

časová složitost je k.N.lb N; nestabilní, nepřirozená, 
implementačně jednoduchá, prostorová složitost úměrná rekurzivnímu
zanoření S=k.lb N

Řazení množinou
---------------

var M: set of TypData;
    d: TypData;

begin M:=[];
      while not eof do begin
         read(d);
         M:=M + [d];
      end;
      for d:=DM to HM do
         if d in M then write(d);
end.

Řazení rozptylováním
--------------------
Hodnoty lib. typu převádíme (rozptylováním) do hodnot ord. typu.

Rozdělovací metody
==================
Rozděl a panuj!

Quick Sort

procedure QuickSort(L,R:word);
var I,J: word;
    X:TypData;
 procedure Rozdel;
  begin
        I:=L; J:=R;
        X:=P[(I+J) div 2];
        repeat
         while P[I]<X do Inc(I);
         while P[J]>X do Dec(J);
         if I<=J then begin
            Zamena(P,I,J);
            Inc(I);
            Dec(J)
         end
        until I>J
  end;

begin Rozdel;
      if L<J then QuickSort(L,J);
      if I<R then QuickSort(I,R)
end;

čas. složitost: k.N.lb N; prost. složitost (rekurze): k.N.lb N

Slučovací metody
================
Merge Sort