Anglická verze
logolink

< Zpět na seznam lekcí

Bubblesort - třídící algoritmus

AlgortimyObsah 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.

bubble sort

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:

Bubblesort
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:

Bubblesort
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.

Bubblesort - základní nejpomalejší varianta
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.

Bubblesort - varianta 2
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

bubblesort

*tento krok vůbec neprobíhá, do tabulky byl uveden jen ilustračně pro úplnost "schodů".

Otázky

  1. Popište princip algoritmu Bubblesort.
webdesign, xhtml, css, php - Mgr. Michal Mikláš