Zadání:

Vytvořte proceduru pro řazení metodou SELECT-SORT.

• Metoda předpokládá, že část pole od indexu 1 až do K je seřazena, a pole od K+1 do MAX je neseřazena. Minimální prvek z druhé části pole se vymění s (K+1)vým prvkem a za seřazenou část uvažujeme 1 - K+1. Na začátku je seřazaná část prázdná a poslední hledání minima se provádí pro prvky (MAX-1) a MAX.
• Metoda je nestabilní.

Procedure SelectSort;
var i,j,k:integer;
    Pom:integer;
begin {SelectSort}
  for i:=1 to Max-1 do begin
    k:=i;
    Pom:=A[k];
    for j:=i+1 to Max do
      if A[j]>Pom then begin
        k:=j;
        Pom:=A[j];
      end; {if}
    A[i]:=:A[k];
  end; {for}
end; {SelectSort}
  

Zadání:

Vytvořte proceduru pro řazení metodou BUBBLE-SORT.

• Princip je podobný jako u SELECT-SORTu, ale odlišný je způsob vyhledání minima a jeho záměna. Neseřazenou část procházíme zprava doleva a porovnáváme dva sousední prvky. Nejsou-li tyto prvky uspořádány dle výsledného seřazení, vyměníme je. Tak minimum "vybublá" na začátek. Řazení končí v okamžiku, kdy v celém průchodu nedošlo k žádné výměně prvků.
• Metoda je stabilní a přirozená.
• Nejrychleji seřadí již seřazené pole.

Procedure BubbleSort;
var i,j:integer;
    konec:boolean;
begin {BubbleSort}
  i:=2;
  repeat
    Konec:=true;
    for j:=Max downto i do
      if A[j-1]>A[j] then begin
        Konec:=false;
        A[j-1]:=:A[j];
      end; {if}
    i:=i+1;
  until Konec or (i=MAX+1);
end; {BubbleSort}
  

Zadání:

Vytvořte proceduru pro řazení metodou HEAP-SORT.

• Za účelem vyhledání maxima definujeme tzv. hromadu, tj. stromovou strukturu, pro kterou platí, že všechny uzly obou podstromů jsou menší než daný uzel. Na vrcholu hromady (v kořeni stromu) je vždy nejvyšší prvek.
  Hromadu implementujeme v poli, které máme řadit.
  Analýzou této struktury zjistíme, že vrchol hromady je prvek na indexu 1 a pro uzel s indexem I platí:
  - index levého syna je 2*I
  - index pravého syna je 2*I+1
  Dále platí, že listem stromu je prvek s indexem K, kde platí, že 2*K>MAX. Pro uzel s indexem K platí, že nemá pravého syna, když (2*K+1)>MAX.

  Procedura, která umí zařadit prvek na správné místo v hromadě, se nazývá SIFT.

• Metoda je nestabilní a nepřirozená.
• Je nejefektivnější z metod založených na principu výběru.

Procedure Sift(L,R:tIndex);
begin {Sift}
  i:=L;
  j:=2*i;  {Index leveho syna}
  X:=A[i];
  Jeste:=j < = R;
  while Jeste do begin
    if j < R then {ma oba syny}
      if A[j+1]>A[j] then j:=j+1; {pravy syn je vetsi}
    if X>=A[j] then
      Jeste:=false                {prvek X je jiz „proset“ na spravne misto}
    else begin
           A[i]:=A[j];
           i:=j;
           j:=2*i;        {prechod na novou uroven}
           Jeste:=j < = R;   {test, zda A[i] je list}
         end;
  end; {while}
  A[i]:=X;
end; {Sift}


Procedure HeapSort;
var L:integer;
begin {HeapSort}
  L:=Max div 2;
  for L:=L downto 1 do sift(L,Max);
  for L:=Max downto 2 do begin
    A[1]:=:A[L];  {Vymena vrcholu hromady a posledniho prvku}
    Sift(1,L-1);  {Znovuustaveni hromady}
  for; {for}
end; {HeapSort}
  

Zadání:

Vytvořte proceduru pro řazení metodou INSERT-SORT.

• Tato metoda vyhledává index, kam se má zařadit prvek a zároveň posouvá pole doprava. Pole musíme rozšířit o zarážku, prvek A[0].
• Metoda je stabilní, chová se přirozeně.

Procedure InsertSort;
var i,j:0..N;
    x:integer;
begin {InsertSort}
  for i:=2 to N do begin
    x:=a[i];
    a[0]:=x;
    j:=i-1;
    while x < a[j] do begin {hledej a posouvej}
                        A[j+1]:=A[j];
                        j:=j-1;
                      end;
    a[j+1]:=x;
  end; {for}
end; {InsertSort}
  

Zadání:

Vytvořte proceduru pro řazení metodou BINARY-INSERT-SORT.

• Metoda vyhledává pozici k vložení prvku pomocí binárního vyhledávání.
• Metoda je stabilní, chová se přirozeně.

Procedure BinaryInsert;
var i,j,m,l,r:0..N;
    x:integer;
begin {BinaryInsert}
  for i:=2 to n do begin
    x:=a[i];
    l:=1;r:=i-1;
    while (l < =r) do begin
      m:=(l+r) div 2;
      if x < a[m] then r:=m-1
                  else l:=m+1;
    end; {while}
    for j:=i-1 downto l do A[j+1]:=A[j]; {posun casti pole}
    a[l]:=x;
  end; {for}
end; {BinaryInsert}
  

Zadání:

Vytvořte proceduru pro řazení metodou QUICK-SORT, a to jak rekurzivní, tak i nerekurzivní metodou.

• Metoda rozdělí pole na již seřazené části a poté se rekurzivně aplikuje na takto vzniklé části. Rozdělení probíhá dle procedury ROZDĚL.
• Metoda není stabilní, nechová se přirozeně.

Procedure Rozdel(var i,j:integer;L,R:integer);
var X:integer;
begin {Rozdel}
  i:=L;j:=R;
  X:=A[(i+j)div 2]; {urcim delici hodnotu}
  repeat
    while A[i] < x do i:=i+1;
    while A[j] > x do j:=j-1;
    if i < = j then begin
                      A[i]:=:A[j];
                      i:=i+1;
                      j:=j-1;
                    end;
  until i>j;
end; {Rozdel}


Procedure QuickSort(L,R:integer);
var i,j:integer;
begin {QuickSort}
  Rozdel(i,j,L,R);
  if L < j then QuickSort(L,j);  {levy interval}
  if i < R then QuickSort(i,R);  {pravy interval}
end; {QuickSort}


Procedure NonRecQuickSort(L,R:integer);
var i,j:integer;
begin {NonRecQuickSort}
  SInit(S);
  Push(S,L);
  Push(S,R);
  while not Sempty(S) do begin
    Top(S,R);Pop(S); 
    Top(S,L); Pop(S);
    while L (j-L)then begin
        Push(S,i);
        Push(S,R);
        R:=j;
      end else begin
        Push(S,L);
        Push(S,j);
        L:=i;
      end; {else}
    end; {while}
  end; {while}
end; {NonRecQuickSort}