Triediace algoritmy

TRIEDIACE ALGORITMY

A/ Priame triedenie 

Triedenie priamym vkladaním 

Princíp:

Triedené pole sa rozdelí na dve časti. Prvá obsahuje už utriedené prvky (na začiatku táto časť obsahuje iba prvý prvok poľa) a druhá obsahuje neutriedené prvky (na začiatku tvorí túto časť celé pole okrem prvého prvku).
Pri triedení sa opakuje postup, v ktorom sa prvý prvok neutriedenej časti vloží na patričné miesto do časti utriedenej. Toto miesto sa získa posunutím všetkých prvkov väčších ako vkladaný prvok na nasledovnú pozíciu v triedenom poli. Pri každom opakovaní sa tak utriedená časť poľa zväčší  a neutriedená časť poľa zmenší jeden prvok. Algoritmus končí vložením posledného prvku poľa na zodpovedajúce miesto.

Ilustrácia činnosti algoritmu pre I=2..6 (červený – vkladaný prvok, zelené – odsúvané prvky)

  For I:=2 to Poc Do              {I=index vkladaného prvku}
    Begin
    Pom:=P[I];  {Do pomocnej premennej uloží vkladaný prvok}
    J:=I-1;    {Pre prvky, umiestnené pred vkladaným prvkom}
    While (J>=1) And (P[J]>Pom) Do
      Begin
      P[J+1]:=P[J]; J:=J-1     {Odsunutie väčších "doprava"}
      End;
    P[J+1]:=Pom {Vloženie odlož. prvku na uprázdnené miesto}
    End

Priama výmena - Buble Sort

Postupujeme od N po 1  a porovnávame hodnoty, ak je prvok menší  vpravo posúvam ho smerom doľava. Potom to vyzerá akoby  to prebublávalo a menšie prvky sa presúvali dopredu.

Princíp:

V utriedenom poli musí pre každú dvojicu susedných prvkov platiť P[i] < P[i+1] (i=1,...,N-1). Algoritmus triedenia priamou výmenou spočíva v opakovanom porovnávaní dvojíc susedných prvkov. Ak tieto prvky nespĺňajú podmienku P[i] < P[i+1], navzájom sa medzi sebou vymenia. Pri porovnávaní susedných dvojíc sa začína porovnaním posledných prvkov poľa P[N-1] a P[N] a končí porovnaním P[1] a P[2]. "Malé" prvky sa pri výmenách posúvajú k začiatku poľa (ako keď ľahké bubliny stúpajú k hladine kvapaliny – odtiaľ  názov algoritmu).
Celý algoritmus končí v najhoršom prípade po N-1 porovnávaniach všetkých dvojíc susedných prvkov. Možno ho však ukončiť i skôr, ak zistíme, že pri porovnávaní všetkých dvojíc susedných prvkov nedošlo k žiadnym výmenám.

Algoritmus:

For I:=2 to Poc Do           {I=kolkýkrát sa "prezerá" pole}
  For J:=Poc DownTo I Do   {J=index prvku, porov. so sused.}
    If P[J-1]>P[J] Then     {Ak treba susedné prvky vymeniť}
      Begin
      Pom:=P[J-1]; P[J-1]:=P[J]; P[J]:=Pom   {Výmena}
      End;

Iné riešenie:

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

Triedenie priamym výberom  - Select Sort

Princíp:

Pole sa rozdelí na časť utriedenú (na začiatku neobsahuje žiaden prvok poľa) a na časť neutriedenú (na začiatku je to celé pole).
Opakuje sa postup, pri ktorom sa z neutriedenej časti vyberie minimálny prvok a tento sa vymení s prvým prvkom neutriedenej časti. Pri každom opakovaní sa takto utriedená časť zväčší o jeden prvok a neutriedená časť sa o jeden prvok zmenší. Pri poslednom opakovaní tohto postupu sa vyberá minimálny prvok medzi poslednými dvomi prvkami poľa a tento sa umiestni na predposlednú pozíciu v poli.

Ilustrácia činnosti algoritmu pre (červeným – kam sa ukladá minimum, zeleným – nájdené minimum)

For I:=1 to Poc-1 Do      {I=koľkýkrát sa vyhľadáva minimum}
  Begin
  PorMin:=I;                  {PorMin=index minimálneho prvku}
  For J:=I+1 To Poc Do  {J určuje, z ktorých sa vyberá min.}
    If P[J]  < Pom then
        begin
         Pom:=P[J];
         PorMin:=J
        End;

   P[PorMin]:=P[I]
   P[I]:=Pom;        {Výmena}

 End;

{Alternatívna verzia – mala by byť rýchlejšia}
For I:=1 to Poc-1 Do
  Begin
  Min:=P[I]; PorMin:=I;
  For J:=I+1 To Poc Do 
    If P[J]
      Begin Min:=P[J]; PorMin:=J End;
  P[PorMin]:=P[I]; P[I]:=Min
  End;

Triedenie priamym vkladaním - InsertSort 

• rozdelenie postupnosti na časť usporiadanú  ( začiatok : 1 prvok )  a neusporiadanú
• prvý prvok neusporiadanej postupnosti vložíme do usporiadanej časti ( zväčší veľkosť o1)
• opakovanie  (POC-1) krát
• použitie  :  pridanie niekoľkých prvkov do už usporiadanej postupnosti
• v takom prípade úprava algoritmu  :  FOR  iba od pridaných
 

FOR I:=2 TO POC DO
  BEGIN
   POM:=P[I];
   J:=I-1;
   WHILE  (POM

B/ Vylepšené metódy –odvodené metódy

Triedenie vkladaním so zmenšovaním kroku  (  ShellSort )

• presuny na väčšiu vzdialenosť sú efektívnejšie
• rozdelenie na postupnosti so vzdialenosťou KROK  ( napr. 5 )
• aplikovanie metódy na každú postupnosť
• zmenšenie kroku  ( ľubovoľným spôsobom,  napr.  KROK=2 )
• opakovanie
• zmenšovanie až na KROK=1  ( treba ešte vykonať metódu )
• závisí na voľbe kroku
• odporúča sa 3, 5, 7, 15, ...  t.j.  ( 2 ^ I  - 1 )
• zmenšovanie kroku    KROK div 2
• použitie : takmer usporiadané, iba niečo neusporiadané

QuickSort    / vylepšený algoritmus triedenia výmenou /

• v postupnosti sa vyberie prvok, tzv. pivot P
• ideálne :  na polovicu  ( medián ),    prakticky : uprostred
• prvky z ľavej časti  ( >P )  sa vymenia s prvkami v pravej časti  (

• vľavo budú menšie,  vpravo väčšie ako pivot
• postupnosť sa rozpadne na dve postupnosti
• opakovanie pre každú podpostupnosť pokiaľ ich dĺžka  >1   ( rekurzia )

zložitosť
• ideálne      O ( n * lg(n) )    ..   medián
• najhoršie    O ( n^2 )   ..   pivot maximum, resp. minimum
• jeden z najčastejšie používaných algoritmov  ( experimentálne overenie : najlepší )

 Pri tomto triedení je uvedený rekurzívny algoritmus:

procedure QSort(var A: array of Integer);
procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do
Inc(Lo);
while A[Hi] > Mid do
Dec(Hi);
if Lo <= Hi then begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then
QuickSort(A, iLo, Hi);
if Lo < iHi then
QuickSort(A, Lo, iHi);
end;
begin
QuickSort(A, Low(A), High(A));
end;

VYHĽADÁVACIE ALGORITMY

Sekvenčné vyhľadávanie:

Hľadáme postupne prvok po prvku:

Algoritmus:

JETOTAM:=False;
i:=1;
Repeat
  if  p[i]  = HL  then  JETOTAM := True
                         else  i:= i+1;
Until JETOTAM or (i >= N);

Binárne vyhľadávanie :

Nájdeme stred poľa a určíme si  ľavý a pravý prvok (ľavý na začiatku sa rovná 1 a pravý N). Takto mame rozdelené pole na dve časti  (ľavu a pravú od stredu) . Zistíme, či prvok patrí do ľavej, alebo pravej časti . Potom nájdeme nový stred a rozdeľujeme pole ďalej až kým nenájdem prvok, ktorý bude zhodný so stredom, aleboz zistíme, že prvok v danej množine nie je.

Algoritmus :

Repeat
  Stredny := (Lavy+Pravy)div 2;
     If  HL <> P[Stredny] then
          If HL< P[Stredny] then Pravy :=Stredny –1
                                         else Lavy := Stredny+1;
Until (HL = P[Stredny])  or  Lavy >Pravy;

Odkazy na animácie ilustrujúce jednotlivé algoritmy:

https://courses.cs.vt.edu/csonline/Algorithms/Lessons/SelectionCardSort/selectioncardsort.swf
https://courses.cs.vt.edu/csonline/Algorithms/Lessons/InsertionCardSort/insertioncardsort.swf
https://www.google.sk/search?hl=sk&q=sort+algorithm+filetype%3Aswf&btnG=H%C4%BEada%C5%A5&meta=&aq=f&oq=
https://www.sorting-algorithms.com/
https://www.inspired.sk/files/flash-films/algoritmy/algoritmy.swf