Bubblesort - třídící algoritmus
Obsah lekce:
- Princip algoritmu
- Bubblesort
Princip algoritmu
Třídicí algoritmus zvaný bubble sort, jak název napovídá, funguje na principu bublinek, které vynáší větší čísla „nahoru“.
Příklad
Uspořádejte čísla 4, 8, 1, 4, 5, 2, 3 postupnými výměnami.
Značka odděluje neuspořádaný úsek (vlevo) od uspořádaného úseku pole. Na začátku třídění je tedy u posledního prvku pole. Procházíme celé pole prvek po prvku od začátku do konce a je-li předcházející prvek větší než následující, vyměníme je. Tím se po prvním průchodu polem dostane (probublá) největší prvek na konec a je posledním prvkem uspořádaného úseku. Značku posuneme o jedno místo dopředu (doleva) a procházíme podruhé neuspořádaný úsek pole (od prvního prvku do značky) a je-li předcházející prvek větší než následující, vyměníme je. Tím se uspořádaný úsek zvětší o druhý prvek (druhý největší). Takto pokračujeme dále. Naposled tento postup opakujeme, je-li značka u druhého prvku. Porovnáme první dva prvky a je-li třeba, vyměníme. Tím bude celé pole seřazené.
Myšlenka (hrubý algoritmus)
Pro značku od posledního zpět do druhého prvku pole opakujeme tuto činnost:
- projít zkoumaný úsek od počátku až do značky (označena proměnou k) a zaměnit ty sousední prvky, které nejsou podle velikosti
Tedy:
for i:=1 to n-1 do
{projdi neusp. úsek, je-li třeba vyměň}
Procházení s eventuální výměnou lze upřesnit takto:
for k:=1 to n-i do
if cisla[ktere]>cisla[ktere+1] then
Bubblesort - nejpomalejší varianta
Tato první varianta algoritmu slouží pouze k tomu, abychom ukázali, jak se dá pouze velmi malou změnou jediného znaku v programu, program velmi zefektivnit.
FOR k:=1 TO n-1 DO
begin
FOR i:=1 TO n-1 DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
end;
end;
Předpokládejme, že máme definované pole p o n prvcích, které naplníme náhodnými čísly a chceme je setřídit podle velikosti.
Při prvním průchodu cyklu FOR má proměnná k i i hodnotu 1 a porovnáváme, zda je první prvek p[i] větší, než prvek následující, tedy p[i+1]. Pokud je podmínka splněna, jsou hodnoty těchto proměnných prohozeny. K tomu slouží tyto tři řádky:
- pom:=p[i]; -> Do pomocné proměnné pom si uložíme hodnotu jednoho prvku.
- p[i]:=p[i+1]; -> Do prvku pole, jehož hodnotu máme uloženou z předchozího kroku, dosadíme hodnotu druhého prvku pole.
- p[i+1]:=pom; -> Na závěr umístíme hodnotu z pomocné proměnné do druhého prvku pole.
Takže teď se nám ukončila podmínka IF a program se vrací zpět k druhému cyklu FOR, kde i už nabylo hodnoty 2. Nyní tedy porovnáváme druhý a třetí prvek stejným způsobem jako předtím.
Až vzroste čítač i na hodnotu, která se rovná hodnotě proměnné n, pak už cyklus neproběhne a program se vrátí zpět k prvnímu cyklu FOR. Zde se čítač k zvedne na hodnotu 2 a opět probíhá přehazování dvojic čísel, opět od prvního k poslednímu.
Tahle varianta třídění je ze všech tří uváděných nejhorší. Program ověřuje seřazení čísel pokaždé od prvního čísla až po poslední a to dokud cyklus FOR s k:=1 to (n-1) nenabude své maximální hodnoty, tedy (n-1). Předpokládejme, že v poli máme 10 000 čísel a ve stejný okamžik si 100 uživatelů zadá příkaz seřazení. Už v tomto okamžiku by operace trvala zbytečně dlouho. Je to zbytečné mrhání časem procesoru.
Bubblesort - varianta 2 aneb záměnou jednoho znaku k 50% nárůstu výkonu
Nyní celý algoritmus zefektivníme tím, že ve druhém cyklu ponecháme cyklus běžet do n-i namísto n-1.
FOR k:=1 TO n-1 DO
begin
FOR i:=1 TO n-i DO
begin
IF p[i]>p[i+1] THEN
begin
pom:=p[i];
p[i]:=p[i+1];
p[i+1]:=pom;
end;
end;
end;
Až vzroste čítač i na hodnotu, která se rovná hodnotě proměnné n, pak už cyklus neproběhne a program se vrátí zpět k prvnímu cyklu FOR. Zde se čítač k zvedne na hodnotu 2 a opět probíhá přehazování dvojic čísel, ale nikoliv k poslednímu, pouze do n-k, protože ta nejvyšší hodnota v poli je vždy na posledním místě už po prvním průchodu prvního cyklu FOR (probublala na poslední místo v poli). Takže již není nutné ji porovnávat, neboť máme jistotu, že již na správném místě.
Jediná věc, která zbývá vysvětlit je, proč první cyklus FOR má probíhat pouze n-1. To proto, protože stačí jednotlivých porovnání provést o jedno méně, než má pole prvků. Pokud si sepíšete čtyři nejvyšší hodnoty pěti-prvkového pole, pak je jasné, že ta pátá hodnota nemůže být vyšší než ony čtyři.
Díky změně z n-1 na n-k už program neověřuje všechna čísla, ale v každém dalším kroku už kontroluje o jedno číslo méně než v kroku předchozím, neboť s každým dalším krokem se hodnota k zvětšuje a tím ubývá čísel, která nejsou ještě seřazena (seřazená čísla přibývají od největšího po nejmenší na pravém konci pole).
Příklad: Máme pole o 5 číslech
*tento krok vůbec neprobíhá, do tabulky byl uveden jen ilustračně pro úplnost "schodů".
Otázky
- Popište princip algoritmu Bubblesort.