Bubblesort

Bubble sort je pomerne hlúpy algoritmus, ktorý sa vyskytuje v podstate len v akademickom svete. Nemá žiadne dobré vlastnosti a je zaujímavý len svojím priebehom, ktorý môže pripomínať fyzikálne alebo prírodné javy. Algoritmus prebieha vo vlnách, pričom pri každej vlne prepadne "najťažšie" prvok na koniec (alebo najľahšia vybuble nahor, záleží na implementáciu). Vlna porovnáva dvojice susedných prvkov a v prípade, že je ľavý prvok väčší ako pravý, prvky prehodí. Algoritmus je stabilný.

Možné zlepšenia

Algoritmus možno napísať úplne hlúpo dvoma vnorenými for cykly s pevne daným počtom opakovaní (obaja by prebehli toľkokrát, ako je v poli prvkov). Keď sa však trochu zamyslíme, zistíme, že je zbytočné porovnávať najťažšie prvky na "dne" polia, pretože sú už na správnom mieste. Vlny si teda môžeme dovoliť postupne skracovať o 1 prvok a tú poslednú teda dokonca úplne vypustiť.

Ďalším zlepšením môže byť kontrola, či pole nie je už náhodou zotriedené, pretože to sa môže ľahko napríklad v polovici behu cyklov stáť a je potom zbytočné v triedení pokračovať. Môžeme si jednoducho nastaviť premennú prehodené na false a pri každom prehodenie nastaviť túto premennú na true. Ak nakonci zistíme, že sme nič neprehodil (premenná má hodnotu false), máme hotovo. Tieto 2 zlepšenie obsahuje ukážkový priebeh a nižšie aj zdrojový kód.

Vrcholnou variantom "bublacího" algoritmu je tzv. Bubble sort s přetřásáním (Shaker sort čiže Cocktail sort), kde v každom behu vnútorného cyklu prebehnú 2 vlny - jedna zľava doprava, tlačiaci ťažšie prvky dole, druhá sprava, vynášajúce ľahší prvky nahor. Odstraňuje to problém tzv. Zajacov a korytnačiek, kde zajace sú ťažké prvky, ktoré sa rýchlo prepadajú dolu. V pôvodnej implementáciu idú však ľahké prvky hore len veľmi pomaly.

Vlastnosti algoritmu

časová zložitosť	O (n ²⁾
stabilita	áno
rýchlosť	veľmi zlá

Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť vzhľadom ku všetkým triediacim algoritmom.

Priebeh

Pretože Bubble sort je trochu neoptimalizované algoritmus, bude priebeh o niečo dlhšia, než bolo doteraz zvykom.

Majme pole nasledujúcich prvkov:

Prvá vlna prejde celým poľom a najväčší prvok "prebublať" na koniec.

Začneme teda s vlnou a porovnáme prvé 2 prvky (3 a 2):

3 je určite väčšia ako 2, preto prvky prehodíme

Porovnáme ďalšie 2 prvky (3 a 5)

Tie sú v správnom poradí, takže je prehadzovať nebudeme. Vlna pokračuje ďalej ...

Po prvej vlne sa maximum (9) naozaj probublalo na koniec. Posledný prvok je teda klasifikované a my si ho už nebudeme všímať. Ďalšie vlna bude o 1 prvok kratšia, než predchádzajúce, a vynesie na koniec maximum z Netriediť časti poľa.

Po druhej vlne máme na konci už 2 zotriedené prvky. Urobíme ďalšiu vlnu.

Vidíme, že pole je teraz zotriedené. Program by urobil ešte jednu vlnu a keď by zistil, že sa nič neprehodil, vrátil by výsledok.

Vizualizácia

Video ukážka

Zdrojový kód

public static void bubbleSort(int[] list) {
  int j = list.length - 2, temp;
  // kontrola prohozeni
  boolean swapped = true;
  while (swapped) {
    swapped = false;
    for (int i = 0; i <= j; i++) {
      // prohozeni
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = true;
      }
    }
    j--;
  }
}

public static void bubbleSort(int[] list) {
  int j = list.Length - 2, temp;
  // kontrola prohozeni
  bool swapped = true;
  while (swapped) {
    swapped = false;
    for (int i = 0; i <= j; i++) {
      // prohozeni
      if (list[i] > list[i + 1]) {
        temp = list[i];
        list[i] = list[i + 1];
        list[i + 1] = temp;
        swapped = true;
      }
    }
    j--;
  }
}

// setridi vlozene pole, predpoklada indexovani od 0
procedure bubble_sort(var list: array of integer);
var i, j, temp: integer;
    swapped: boolean;
begin
  j:=length(list) - 2;
  // kontrola prohozeni
  swapped:=true;
  while swapped do begin
    swapped:=false;
    for i:=0 to j do
      // prohozeni prvku
      if (list[i] > list[i + 1]) then begin
        temp:=list[i];
        list[i]:=list[i + 1];
        list[i + 1]:=temp;
        swapped:=true;
      end;
    dec(j);
  end;
end;

# vraci setridene pole
def bubble_sort(list)
   j = list.length - 2
   # kontrola prohozeni
   swapped = true
   while (swapped) do
     swapped = false
     (j + 1).times do |i|
       # prohozeni
       if (list[i] > list[i + 1])
         temp = list[i]
         list[i] = list[i + 1]
         list[i + 1] = temp
         swapped = true
       end
     end
     j -= 1
  end
end

Článok pre vás napísal David Hartinger

Užívateľské hodnotenie:

Ešte nikto nehodnotil, buď prvý!

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.

Aktivity