čo sa budeme dnes učiť

• rôzne algoritmy triedení
• spúšťanie paralelného procesu - vlákna

Triedenia

Algoritmus triedenia má za úlohu vzostupne (alebo zostupne) usporiadať nejakú údajovú štruktúru podľa niektorých hodnôt. Pre jednoduchosť budeme vzostupne usporadovať postupnosť celých čísel. U všetkých triedení okrem triedenia zlučovaním (MergeSort) budeme triediť jednorozmerné N-prvkové celočíselné pole p a niekedy použijeme pomocnú procedúru vymeň

var
  p:array[0..N-1] of integer;

procedure vymen(i,j:integer);
var
  t:integer;
begin
  t:=p[i]; p[i]:=p[j]; p[j]:=t;
end;

Pri rôznych algoritmoch triedení nás bude zaujímať ako efektívne tento pracuje. Pre malý počet prvkov asi nie je veľmi podstatné, či algoritmus bežal 5 alebo 6 milisekúnd, ale pre väčšie postupnosti hodnôt (napr. milión) už môže zavážiť, či triedenie pobeží 30 alebo 1 000 000 sekúnd. Vzhľadom na efektívnosť algoritmu sú dôležité informácie napr. o počte porovnávaní a počte výmen medzi prvkami.

Môžete si stiahnuť demonštračný projekt na vizualizáciu priebehu triedení - v projekte môžete nastavovať konštanty sir, bod a cas a odkomentovaním niektorého z triedení ho môžete otestovať.

Bublinkové triedenie (BubbleSort)

skoro najhoršie aké môže byť - môžeme ho použiť len pre malé polia v situácii, keď nezáleží na rýchlosti

Porovnávanie dvoch prvkov vedľa seba - do prvku poľa s menším indexom ide menší z nich. Po jednom prechode poľom sa určite maximálny prvok dostane na koniec poľa. Potom ostáva utriediť N-1 prvkov poľa (posledný je už na svojom mieste):

procedure BubbleSort;
var
  i,j:integer;
begin
  for i:=N-2 downto 0 do
    for j:=0 to i do
      if p[j] > p[j+1] then vymen(j,j+1);
end;

Pozn.

• počet výmen je v "najhoršom prípade" N*(N-1)/2

MinSort

Nájde v úseku poľa minimálny prvok, vymení ho s prvým prvkom úseku a posunie dolnú hranicu triedeného úseku o 1 (t.j. triedený úsek poľa sa skráti o 1), atď.

procedure MinSort;
var
  i,j,min:integer;
begin
  for i:=0 to N-2 do begin
    min:=i;
    for j:=i+1 to N-1 do
      if p[j] < p[min] then min:=j;
    vymen(i,min);
  end;
end;

Pozn.

• porovnaní je rovnako ako pri triedení BubbleSort, ale výrazne menej výmen (maximálne N-1)
• toto triedenie môžeme použiť vtedy, keď porovnanie dvoch prvkov poľa je rýchle a pomalú výmenu dvoch prvkov potrebujeme urobiť čo najmenejkrát

Triedenie vsúvaním (InsertSort)

Istá časť poľa je už utriedená, zaradí nový prvok na svoje miesto a predĺži utriedený úsek o 1

procedure InsertSort;
var
  i,j,t:integer;
begin
  // predpoklad v cykle:
  //    0..i-1 je utriedený úsek, vsuň p[i] tak, aby ostal utriedený
  for i:=1 to N-1 do begin
    j:=i-1; t:=p[i];
    while (j>=0) and (p[j]>t) do begin  // hľadanie vhodného miesta pre prvok p[i]
      p[j+1]:=p[j];
      dec(j);
    end;
    p[j+1]:=t;
  end;
end;

Pozn.

• opäť je to veľmi pomalý algoritmus - porovnateľný s BubbleSortom

Triedenie zlučovaním (MergeSort)

• metóda rozdeľuj a panuj, t.j. ľahšie sa utriedi menej položiek ako veľa
• algoritmus
• pole rozdelíme na dve približne rovnako veľké časti (pri nepárnom počte je jedna časť väčšia)
• potom sa zaoberajme s každou z týchto dvoch častí zvlášť a to takým istým spôsobom, t.j. rozdelíme ju na dve časti
• znovu vezmime prvú z nich a rozdeľme ju na dve, atď. ... až kým nedostaneme jednoprvkové úseky
• je zrejmé, že jedna položka je utriedená a teda máme dve utriedené časti
• teraz použijeme druhú časť algoritmu: zlúčenie dvoch utriedených častí tak, aby aj novovzniknutá časť bola utriedená, t.j. dostávame časť s dvoma položkami
• podobne sa rozdelí a zlúči aj druhá časť z rozdelenia a dostávame utriedenú druhú dvojprvkovú časť
• ten istý algoritmus zlúčenia dvoch utriedených častí použijeme aj teraz a dostávame utriedenú štvorprvkovú časť ...
• algoritmus sa bude opakovať, až kým nebude utriedené celé pole
• toto triedenie sa používa najmä pri triedení prvkov spájaných zoznamov - zlučovanie dvoch polí bez pomocného poľa je veľmi náročná operácia a môže pokaziť efektívnosť celého algoritmu
• toto triedenie patrí medzi tzv. rýchle triedenia - "efektívnosť" je rádovo N*log₂ N

type
  TZoznam = class
    h:integer;
    next:TZoznam;
  end;

procedure MergeSort(var z:TZoznam);

  procedure rozdel(p:TZoznam; var dp:TZoznam);
  var
    stred,pom:TZoznam;
  begin
    if p=nil then dp:=nil           // nebolo čo deliť
    else begin
      stred:=p;
      pom:=stred.next;
      while pom<>nil do begin       // pokiaľ nie je na konci zoznamu
        pom:=pom.next;              // posuň sa o jeden krok
        if pom<>nil then begin      // ešte nie som na konci
          stred:=stred.next;        // posuň stred o jeden krok
          pom:=pom.next;            // posuň sa o druhý krok
        end;
      end;
      dp:=stred.next;               // vráť smerník na prvok, ktorý je stredný
      stred.next:=nil;              // zmodifikuj pôvodný dlhý zoznam na polovičný
    end;
  end;

  procedure zluc(p1,p2:TZoznam; var p:TZoznam);
  var
    k:TZoznam;
  begin
    if p1=nil then p:=p2           // ak je zoznam p1 prázdny
    else if p2=nil then p:=p1      // ak je zoznam p2 prázdny
    else begin                     // oba zoznamy sú neprázdne
      if p1.h <= p2.h then begin   // vyriešme prvý prvok nového zoznamu
        p:=p1;
        p1:=p1.next;
      end
      else begin
        p:=p2;
        p2:=p2.next;
      end;
      k:=p;   // vytvárame zoznam p pridávaním na koniec pomocou pomoc. smerníka k
      while (p1<>nil) and (p2<>nil) do
        if p1.h <= p2.h then begin
          k.next:=p1; k:=p1; p1:=p1.next;
        end
        else begin
          k.next:=p2; k:=p2; p2:=p2.next;
        end;
      if p1=nil then k.next:=p2   // vyprázdnil sa zoznam p1
      else k.next:=p1;            // vyprázdnil sa zoznam p2
    end;
  end;

var
  druhapol:TZoznam;
begin
  if (z<>nil) and (z.next<>nil) then begin     // aspoň 2 prvky
    rozdel(z,druhapol);
    MergeSort(z);
    MergeSort(druhapol);
    zluc(z,druhapol,z);
  end;
end;

Pozn.

• rekurzívna procedúra MergeSort spracuje celý zoznam tak, že ho rozdelí na dve časti s približne rovnakým počtom prvkov, na tieto zavolá tú istú procedúru (pokiaľ sú zoznamy viac ako jednoprvkové) a potom takto vzniknuté zoznamy zlúči
• procedúra rozdel sa bude snažiť nájsť "polovicu" celého zoznamu, ktorý dostáva cez smerník p a vráti dva zoznamy s približne rovnakým počtom prvkov, stred sa bude hľadať tak, že po zozname budú "putovať" dva smerníky, jeden po jednom kroku a druhý po dvoch, a ak sa druhý smerník prepracuje na koniec zoznamu, zrejme prvý, ktorý šiel po kroku, bude práve v polovici zoznamu
• ak máme dobre rozdelený zoznam na dve časti a vraciame sa z rekurzie ostáva nám iba dobre tieto dve časti zlúčiť a to tak, aby aj nový, dlhší zoznam, ostal utriedený; procedúra zluc teda prechádza oboma zoznamami a vytvára z nich nový

NDÚ:

• usporiadať v poli pomocou pomocného poľa
• usporiadať v poli bez pomocného poľa (asi bude priveľa posunov poľa)
• triediť binárny súbor s dvoma pomocnými súbormi
• triediť zoznam (alebo pole) bez rekurzie

Rýchle triedenie (QuickSort)

• v predchádzajúcom triedení sme museli zoznamy dobre zlúčiť
• triedenie QuickSort vytvára dve časti poľa tak, aby ich nebolo treba zlučovať, ale aby ich stačilo iba položiť za seba:
• v prvom kroku sa jeden prvok vyberie za pivota (v princípe to môže byť ľubovoľný prvok, my vyberme prvý prvok z danej postupnosti)
• podľa tohto pivota rozdeľme vstupnú postupnosť prvkov na dve časti, pričom v prvej z nich budú čísla menšie ako pivot a v druhej čísla väčšie a rovné ako pivot (v najlepšom z prípadov sa postupnosť rozdelí na dve časti, s približne rovnakým počtom prvkov, v najhoršom prípade však zrejme na nula prvkov, ktoré bude tvoriť prvú časť a na všetky ostatné prvky)
• po takomto rozdelení postupnosti dostávame tri časti - časť s jediným prvkom, ktorým je pivot, časť, v ktorej sú prvky menšie ako pivot, a časť s prvkami väčšími alebo rovnými ako je pivot
• potom rovnakým spôsobom utriedime druhú časť (prvky menšie ako pivot) a tretiu časť (prvky väčšie ako pivot)
• po ich utriedení druhú a tretiu časť "položíme" vedľa seba, pričom pivot dáme na správne miesto

procedure QuickSort;

  procedure rozdel(z,k:integer; var ip:integer);
  var
    pivot:integer;
    i:integer;
  begin
    pivot:=p[z]; ip:=z;         // pivot je prvý prvok
    for i:=z+1 to k do          // prejdi všetky prvky medzi z+1 a k
      if p[i]<pivot then begin  // pozeraný prvok patrí do prvej časti poľa
                                // je o jeden viac takých, čo sú menšie ako pivot
        inc(ip); vymen(ip,i);
      end;
    vymen(z,ip);                // daj pivot na správne miesto
                                // v ip je index, na ktorom je umiestnený pivot
  end;

  procedure quick(z,k:integer);
  var
    ipivot:integer;
  begin
    if z>=k then exit;
    rozdel(z,k,ipivot);
    quick(z,ipivot-1);
    quick(ipivot+1,k);
  end;

begin
  quick(0,N-1);
end;

Pozn.

• procedúra quick je rekurzívna a triedi časť poľa medzi indexmi z a k, pričom najprv volá procedúru rozdel na rozdelenie tejto časti a zistenie indexu pivota, potom aplikuje ten istý algoritmus na časť poľa pred indexom, na ktorom je pivot a na časť poľa za pivotom
• procedúra rozdel dáva prvky menšie ako pivot na začiatok poľa, prvky väčšie alebo rovné ako pivot na koniec poľa a po skončení tohto upratovania dá ešte pivot na správne miesto a vráti jeho index
• ak bolo pole utriedené ešte pred samotným triedením, tak je zvolený najhorší možný pivot, preto sa na začiatku rozdel zvykne pridať:
     vymen(z,(z+k) div 2);

NDÚ:

• v praxi sa väčšinou používa bez rekurzie - preprogramujte toto triedenie bez rekurzie
• triediť spájaný zoznam
• triediť binárny súbor

Triedenie haldou (HeapSort)

• budeme triediť pole
• halda je dátová štruktúra, ktorá
• má tvar "skoro" úplného binárneho stromu (len na poslednej úrovni binárneho stromu môžu chýbať synovia (vrcholov predposlednej úrovne) a to tak, že ak chýba nejaký syn tak budú chýbať aj všetci synovia vpravo na najnižšej úrovni;
• pre všetky vrcholy stromu platí, že otec má väčšiu (alebo rovnú) hodnotu ako jeho synovia - ak existujú
• zrejme v koreni haldy je vždy maximálny prvok
• haldu budeme reprezentovať v jednorozmernom poli indexovanom od 0 tak, že koreň stromu je na indexe 0 a i-ty vrchol má synov na indexoch 2*i+1 a 2*i+2
• dve fázy algoritmu
• vytvorenie haldy
• v halde je koreň (t.j. prvý prvok poľa) najväčší prvok zo všetkých, jeho výmena s posledným prvkom (ešte neutriedeného) poľa a nové "uhaldovanie", t.j. oprava haldy
• zakaždým pracujeme s o 1 kratším poľom - haldou -> na jeho konci sa postupne sústreďujú najväčšie prvky

procedure HeapSort;

  procedure posun(var i:integer; m:integer);
  begin                      // ak existuje syn -> nastaví sa na väčšieho z nich
    if 2*i+1<=m then begin   // aspoň jeden syn existuje
      i:=2*i+1;              // v i je ľavý syn
      if (i<m) and (p[i+1]>p[i]) then i:=i+1
          // pravý syn bol väčší a preto je v i pravý syn inak ostáva v i ľavý syn
    end;
  end;

  procedure uprac_haldu(k,m:integer);
  var
    i:integer;    // predpokladáme, že od k+1 do m to už halda je - pridáme k-ty
  begin
    i:=k; posun(i,m);
    while p[k]<p[i] do begin
      vymen(k,i);
      k:=i;
      posun(i,m);        // v i je nový väčší syn
    end;
  end;

  procedure vytvor_haldu;
  var
    i:integer;
  begin
    for i:= (N-1) div 2 downto 0 do uprac_haldu(i,N-1)
  end;

var
  i:integer;
begin
  vytvor_haldu;
  i:=N-1;                // ber postupne všetky prvky
  while i>0 do begin
    vymen(0,i);          // vymeň koreň a posledný zatiaľ neutriedený - í-ty prvok
    dec(i);              // zmenši rozmer stromu
    uprac_haldu(0,i);    // oprav strom - koreň je asi zlý
  end;
end;

Pozn.

• procedúra uprac_haldu vytvára haldu v poli medzi zadanými dvoma indexmi poľa, t.j. po jej skončení je časť poľa K až M haldou, pričom procedúra predpokladá, že časť K+1 až M je halda, ale tým, že sme pridali prvok na miesto K, mohla sa halda K až M pokaziť a preto treba pole znovu "uhaldovať", t.j. zabezpečiť, aby aj pre K platilo, že má oboch synov menších ako on sám (ak to tak nie je, treba ho zrejme vymeniť s väčším zo synov a postup opakovať pre tohto syna a príslušný podstrom)
• pomocná procedúra posun posúva prvý parameter na väčšieho syna

NDÚ:

• namiesto triedenia prvkov poľa prehadzovaním hodnôt realizujte triedenie len pomocou triedenia indexov poľa, t.j. vytvoríte pole čísel od low(p) až do high(p) (indexové pole) a toto pole preusporiadate tak (vytvoríte jeho permutáciu), že napr. jeho výpis v poradí indexov v tomto poli vypíše usporiadané pole
• takéto triedenie realizujte pre všetky doteraz známe triedenia
• napíšte program, ktorý porovná rýchlosť rôznych triediacich algoritmov pre to isté pole celých čísel; môžete použiť napr. funkciu Time, ktorá vracia  momentálny čas; testujte to pre rôzne veľké polia náhodných čísel (napr. 10000 až 1000000 prvkov)

RadixSort

• triedenie po cifrách:
• pripravíme K pomocných kôpok, do ktorých budeme prehadzovať hodnoty zo vstupnej postupnosti
• K - počet rôznych hodnôt, ktoré môžu nadobúdať jednotlivé cifry (napr. pre čísla 10, pre znaky 26 a pod.)
• v prvom prechode postupne prehadzujeme všetky hodnoty do príslušnej kôpky podľa poslednej cifry
• potom všetky kôpky spojíme - zoradíme opäť do jednej postupnosti
• v druhom prechode prehadzujeme hodnoty do kôpok podľa predposlednej cifry
• opäť ich potom spojíme do jednej postupnosti
• toto postupne opakujeme pre všetky cifry - na záver je celá postupnosť utriedená vzostupne
• takto sa dobre triedia spájané zoznamy
• pri práci s poliami si tento algoritmus vyžaduje veľa pomocných polí

NDÚ:

• naprogramujte toto triedenie pre spájané zoznamy, pole, binárny súbor

Thread - vlákna

• operačný systém Windows dovolí spustiť dve alebo viac procedúr naraz a tiež nám umožňuje, aby toto riadil náš program - tomuto sa hovorí multithreading ("viac vláken")
• trieda TThread (vlákno) umožňuje písanie paralelných aplikácií
• keď chceme, aby niečo bežalo paralelne, vyrobíme tomu inštanciu triedy, ktorá je potomkom TThread (samotná trieda TThread je abstraktná a nevie robiť nič konkrétne)
• konštruktor TThread má logický parameter, ktorým oznámime, či sa má vlákno (thread) spustiť hneď pri vytvorení alebo až neskôr zavolaním metódy Resume (true znamená, že proces je v pozastavenom stave (Suspend) a treba ho oživiť metódou Resume)
• spustenie vlákna (threadu) znamená, že sa spustí telo metódy Execute (táto je v TThread definovaná ako virtual a abstract)
• keď vlákno (thread) potrebuje pracovať s formulárom (vykresliť niečo, nastaviť komponent, ...), musí byť synchronizovaný s hlavným vláknom (threadom) (stará sa o naše formuláre, zabezpečuje klikania myšou a všetky ostatné udalosti) - pomocou metódy Synchronize - táto má procedurálny parameter, ktorým je metóda bez parametrov

Nasledujúci príklad demonštruje jednoduché použitie vlákna (threadu). V triede TBodkujThread definujeme metódu Execute (telo paralelne bežiacej procedúry), ktorá bude donekonečna (alebo kým nebude požiadavka vlákno (thread) ukončiť - Terminated) kresliť bodky do plochy (Canvasu) formulára.

type
  TForm1 = class(TForm)
    Start: TButton;         // vo formulári sú dve tlačidlá START a STOP
    Stop: TButton;
    procedure StartClick(Sender: TObject);
    procedure StopClick(Sender: TObject);
    ...
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

type
  TBodkujThread = class(TThread)
  private
    procedure cosi;
  protected
    procedure Execute; override;
  end;

procedure TBodkujThread.cosi;
begin
  with Form1 do
    Canvas.Pixels[random(ClientWidth),random(ClientHeight)]:=clRed;
end;

procedure TBodkujThread.Execute;
begin
  repeat
    Synchronize(cosi);
  until Terminated;
end;

//////////////////////////////////////////////

var
  bodkovanie:TThread;      // mohlo byť aj bodkovanie:TBodkujThread;

procedure TForm1.startClick(Sender: TObject);
begin
  start.Enabled:=false;
  stop.Enabled:=true;
  bodkovanie:=TBodkujThread.Create(false);    // hneď sa aj spustí
end;

procedure TForm1.stopClick(Sender: TObject);
begin
  start.Enabled:=true;
  stop.Enabled:=false;
  bodkovanie.Free;
end;

procedure TForm1.FormMouseDown(...);
begin
  if not (ssLeft in Shift) then exit;
  Canvas.Pen.Width:=20;
  Canvas.Pen.Color:=clBlue;
  Canvas.MoveTo(x,y);
  Canvas.LineTo(x,y);
end;

procedure TForm1.FormMouseMove(...);
begin
  if not (ssLeft in Shift) then exit;
  Canvas.LineTo(x,y);
end;

Pozn.

• metódy FormMouseDown aj FormMouseMove umožňujú kresliť do formulára aj počas bodkovania paralelným procesom
• všimnite si, že virtuálna metóda Execute nie je ani private ani public - je v časti protected - to znamená, že je niečo ako private - ale pre programátorov, ktorí budú programovať odvodené triedy z TThread je to normálne prístupná metóda a pre všetkých ostatných je to private

Application.onIdle

Takýto istý efekt sa dá urobiť aj bez vlákna - pomocou udalosti onIdle (využitie času, keď aplikácia nič nerobí)

type
  TForm1 = class(TForm)
    Start: TButton;
    Stop: TButton;
    procedure StartClick(Sender: TObject);
    procedure StopClick(Sender: TObject);
    ...
  private
    procedure bodkuj(Sender: TObject; var Done: Boolean);
  end;

...

procedure TForm1.bodkuj(Sender: TObject; var Done: Boolean);
begin
  Canvas.Pixels[random(ClientWidth),random(ClientHeight)]:=clRed;
  Done:=false;
end;

procedure TForm1.startClick(Sender: TObject);
begin
  start.Enabled:=false;
  stop.Enabled:=true;
  Application.OnIdle:=bodkuj;
end;

procedure TForm1.stopClick(Sender: TObject);
begin
  start.Enabled:=true;
  stop.Enabled:=false;
  Application.OnIdle:=nil;
end;

procedure TForm1.FormMouseDown(...);
begin
  if not (ssLeft in Shift) then exit;
  Canvas.Pen.Width:=20;
  Canvas.Pen.Color:=clBlue;
  Canvas.MoveTo(x,y);
  Canvas.LineTo(x,y);
end;

procedure TForm1.FormMouseMove(...);
begin
  if not (ssLeft in Shift) then exit;
  Canvas.LineTo(x,y);
end;

Preteky triedení

Keď už vieme vytvárať a spúšťať paralelné procedúry, môžeme zrealizovať preteky rôznych triedení, pričom budeme tieto triedenia vizualizovať. Každá hodnota v poli bude v grafickej ploche (Image) zobrazená buď farebnou bodkou alebo úsečkou (ako v histograme). Výmena dvoch prvkov v poli alebo priradenie nejakej hodnoty do prvku poľa sa bude realizovať pomocnými metódami vymen, resp. prirad, ktoré budú zároveň prekresľovať grafickú plochu.

Do formulára umiestnime 6 rovnako veľkých Image (napr. 300x200) a štartovacie tlačidlo

type
  TForm1 = class(TForm)
    Image1: TImage;
    Image2: TImage;
    Image3: TImage;
    Image4: TImage;
    Image5: TImage;
    Image6: TImage;
    Start: TButton;
    procedure StartClick(Sender: TObject);
  private
    s:array[1..6] of TThread;
  end;

var
  Form1: TForm1;

implementation

uses
  SortThread, bubblesort, minsort, insertsort, mergesort, quicksort, heapsort;

{$R *.DFM}

procedure TForm1.StartClick(Sender: TObject);
var
  p:pole;
  i:integer;
begin
  DoubleBuffered:=true;
  start.Enabled:=false;
  SetLength(p,Image1.Width);
  randomize;
  for i:=0 to high(p) do p[i]:=random(Image1.Height);
  s[1]:=TBubbleSort.Create(p,Image1);
  s[2]:=TMinSort.Create(p,Image2);
  s[3]:=TInsertSort.Create(p,Image3);
  s[4]:=TMergeSort.Create(p,Image4);
  s[5]:=TQuickSort.Create(p,Image5);
  s[6]:=THeapSort.Create(p,Image6);
  for i:=1 to 6 do s[i].Resume;            // až tu sa to naraz všetko odštartuje
end;

Všetky typy triedení vytvoríme ako potomka abstraktnej triediacej triedy TSortThread - táto obsahuje všetko, čo potrebuje paralelne vykonávané triedenie (napr. zobrazovanie, vymieňanie prvkov, inicializáciu a pod.) okrem samotného triedenia - metódy sort - táto bude dodefinovaná až v potomkoch tejto triedy.
Najlepšie sa robí nová thread-trieda tak, že cez menu File/New... zvolíme Thread Object -> vytvorí sa unit, ktorý obsahuje schému threadu - túto ďalej dorobíme 

unit SortThread;

interface

uses
  Classes, Graphics, ExtCtrls;

type
  pole=array of integer;        // array[0..N-1] of integer;

  TSortThread = class(TThread)
  private
    g:TCanvas;
    vi,vj,vys:integer;          // vys je výška grafickej plochy
    ff:TColor;
    pp:pole;
    function dajN:integer;
    function dajp(ix:integer):integer;
    procedure prirad(i,hodn:integer);
    procedure KresliPrvok(i:integer; f:TColor);
    procedure synchroprirad;
    procedure Kresli(f:TColor);
    procedure synchroKresli;
  protected                     // môžu byť používané len v potomkoch TSortThread
    procedure vymen(i,j:integer);
    procedure Sort; virtual; abstract;
    procedure Execute; override;
    property p[ix:integer]:integer read dajp write prirad;
    property N:integer read dajN;
  public
    constructor Create(const np:pole; im:TImage);
  end;

implementation

{ TSortThread }

constructor TSortThread.Create(const np:pole; im:TImage);
begin
  inherited Create(true);      // vlákno sa hneď nespustí - bude treba Resume
  pp:=copy(np,0,Length(np));
  vys:=im.Height;
  g:=im.Canvas;
  Kresli(clBlue);
  Priority:=tpLowest;
  FreeOnTerminate:=true;       // objekt sa automaticky uvoľní po skončení Execute
end;

function TSortThread.dajp(ix:integer):integer;
begin
  Result:=pp[ix];
end;

function TSortThread.dajN:integer;
begin
  Result:=Length(pp);
end;

procedure TSortThread.KresliPrvok(i:integer; f:TColor);
begin
//  g.Pixels[i,vys-pp[i]-1]:=f;    // keď chceme vykresľovať iba bodky
  g.Pen.Color:=f; g.MoveTo(i,vys); g.LineTo(i,vys-pp[i]-1);
end;

procedure TSortThread.vymen(i,j:integer);
var
  t:integer;
begin
  if i=j then exit;
  t:=pp[i]; p[i]:=pp[j]; p[j]:=t;
end;

procedure TSortThread.prirad(i,hodn:integer);
begin
  if pp[i]=hodn then exit;
  vi:=i; vj:=hodn;
  Synchronize(synchroprirad);
end;

procedure TSortThread.synchroprirad;
begin
  KresliPrvok(vi,clWhite);
  pp[vi]:=vj;
  KresliPrvok(vi,clBlue);
end;

procedure TSortThread.Execute;
begin
  Sort;
//  Kresli(clRed);
end;

procedure TSortThread.Kresli(f:TColor);
begin
  ff:=f;
  Synchronize(synchroKresli);
end;

procedure TSortThread.synchroKresli;
var
  i:integer;
begin
  for i:=0 to high(pp) do
    KresliPrvok(i,ff);
end;

end.

unit bubblesort;

interface

uses
  SortThread;

type
  TBubbleSort = class(TSortThread)
  protected
    procedure Sort; override;
  end;

implementation

procedure TBubbleSort.Sort;
var
  i,j:integer;
begin
  for i:=N-2 downto 0 do
    for j:=0 to i do
      if p[j]>p[j+1] then vymen(j,j+1);
end;

end.

MergeSort môžeme prerobiť tak, aby sa dal vizualizovať, t.j. bez spájaného zoznamu - použili sme tu pomocné pole

procedure TMergeSort.Sort;

  procedure zluc(z,s,k:integer);
  var
    pom:pole;
    i,i1,i2:integer;
  begin
    SetLength(pom,k-z+1);
    for i:=0 to k-z do pom[i]:=p[z+i];

    i1:=z; i2:=s+1;
    for i:=z to k do
      if (i1>s) or ((i2<=k) and (pom[i1-z]>pom[i2-z])) then
        begin p[i]:=pom[i2-z]; inc(i2) end
      else
        begin p[i]:=pom[i1-z]; inc(i1) end;
  end;

  procedure merge(z,k:integer);
  var
    stred:integer;
  begin
    if z>=k then exit;
    stred:=(z+k) div 2;    // rozdeľ
    merge(z,stred);
    merge(stred+1,k);
    zluc(z,stred,k);
  end;

begin
  merge(0,N-1);
end;

NDÚ:

• skompletizujte program na preteky triedení
• pokúste sa navrhnúť spôsob zobrazenia prvkov v poli, ak ich bude viac ako šírka príslušného Image (napr. v jednom stĺpci bude viac prvkov)
• pokúste sa navrhnúť program tak, aby sa dalo zvoliť, ktoré triedenie bude v ktorej Image-ploche, resp. aké pole sa bude triediť (napr. náhodne generované, vzostupne usporiadané, zostupne usporiadané, pole s rovnakými prvkami a pod.)
• ak do metódy Execute za vyvolanie metódy Sort dáte nejaké príkazy, tieto sa vykonajú až po skončení príslušného triedenia - môžete sem dať napr. vykreslenie poľa inou farbou (metóda Kresli), alebo aj kontrolu, či je pole správne usporiadané
• nájdite v literatúre, resp. vymyslite sami nejaké iné triedenia a porovnajte ich priebeh s doteraz známymi triedeniami (napr. RadixSort, TreeSort, ShakerSort, ...)

Pozn.:

• vykresľovanie priebehu môžeme urýchliť tak, že aj metódu vymen triedy TSortThread zrealizujeme jediným "synchronizovaním", t.j. nebude sa v nej dvakrát volať prirad, napr.

procedure TSortThread.vymen(i,j:integer);
begin
  if i=j then exit;
  vi:=i; vj:=j;
  Synchronize(synchrovymen);
end;

procedure TSortThread.synchrovymen;
var
  t:integer;
begin
  KresliPrvok(vi,clWhite);
  KresliPrvok(vj,clWhite);
  t:=pp[vi]; pp[vi]:=pp[vj]; pp[vj]:=t;
  KresliPrvok(vi,clBlue);
  KresliPrvok(vj,clBlue);
end;