Bubble-sort
Triedenie Bubble-sort, nazývané aj triedenie výmenou, je algoritmus, ktorý je založený na porovnávaní susedných prvkov poľa. Pri vzostupnom usporiadaní si prvky vymenia pozície ak je nasledujúci prvok menší ako predchádzajúci. V prvok kroku (porovnávaní) sa na poslednú pozíciu dostane najvyšší (najväčší) prvok v zadanom poli. Ostatné prvky poľa môžu zostať na svojich nezmenených miestach v závislosti od prvku, s ktorým boli porovnávané. V ďalších krokoch sa nemusia porovnať všetky susedné dvojice, nakoľko sa niektoré prvky mohli zoradiť v niektorom z predchádzajúcich krokov. Po každom kroku sa správne usporiada vždy aspoň jeden prvok poľa. Teraz si ukážeme postup Bubble-sort triedenia. Máme pole s ôsmimi číselnými prvkami 4, 8, 7, 3, 5, 9, 1 a 2. Najnižšia hodnota daného poľa je číslo jeden a najvyššia hodnota je číslo deväť. Logicky nám vyplýva, že na prvom mieste (úplne vľavo) teda bude číslo jeden a na poslednom mieste vpravo bude číslo deväť. Začneme porovnaním prvých dvoch prvkov:
= 4 < 8 => pozícia prvkov sa nemení
= 8 < 7 => neplatí, prvky si vymenia pozície
= 8 < 3 => neplatí, prvky si vymenia pozície
= 8 < 5 => neplatí, prvky si vymenia pozície
= 8 < 9 => pozícia prvkov sa nemení
= 9 < 1 => neplatí, prvky si vymenia pozície
= 9 < 2 => neplatí, prvky si vymenia pozície
= konečné umiestnenie prvku (ukončený krok)
Keď je najvyšší prvok na poslednom mieste poľa, cyklus triedenia sa opätovne spustí. Na obrázku dole môžeme vidieť ako sa budú jednotlivé prvky usporadovať podľa hodnoty od najnižšej po najvyššiu po každom spustení cyklu triedenia.
Vidíme, že prvky sme mali správne zoradené už pri šiestom spustení cyklu. Cyklus triedenia ale musí prebehnúť ešte raz, keďže nemá odkiaľ vedieť, že prvky na prvých dvoch miestach sú správne zoradené. Preto sa triedenie spustí ešte raz a skontroluje sa správne umiestnenie prvých dvoch prvkov. Ak si spočítame koľkokrát cyklus prebehol, zistíme, že pri osemprvkovom poli prebehne sedemkrát, čo znamená, že pri poli s množstvom prvkov n sa cyklus triedenia Bubble-sort spustí n-1-krát. Teraz si skúsime toto triedenie naprogramovať.
Ako prvé si vytvoríme
pole desiatich náhodných prvkov, ktoré si vypíšeme na grafickú plochu. Potom
privoláme procedúru BubbleSort. V tej sme si definovali, aby procedúra
postupne prechádzala jednotlivé prvky poľa. Stačí nám n-1 prechodov po poli. V prípade, že aktuálny prvok je väčší
ako nasledujúci, vymenia si pozície. Takto cyklus prejde postupne každý prvok
s tým, že ak podmienka nie je splnená, teda aktuálny prvok je menší ako
nasledujúci, cyklus si zapamätá pozíciu tohto prvku a začne proces
odznovu. Vieme, že postačí, ak sa začne triediť zvyšok neusporiadaného poľa,
teda sa zopakuje n-i prechodov.
