NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 2 - Bubblesort

V minulé lekci, Selection sort, jsme se seznámili s průběhem třídění prvků pomocí algoritmu Selection Sort.

Bubble sort je poměrně hloupý algoritmus, který se vyskytuje v podstatě jen v akademickém světě. Nemá žádné dobré vlastnosti a je zajímavý pouze svým průběhem, který může připomínat fyzikální nebo přírodní jevy. Algoritmus probíhá ve vlnách, přičemž při každé vlně propadne "nejtěžší" prvek na konec (nebo nejlehčí vybublá nahoru, záleží na implementaci). Vlna porovnává dvojice sousedních prvků a v případě, že je levý prvek větší než pravý, prvky prohodí. Algoritmus je stabilní.

Možná zlepšení

Algoritmus lze napsat úplně hloupě dvěma vnořenými for cykly s pevně daným počtem opakování (oba by proběhly tolikrát, jako je v poli prvků). Když se však trochu zamyslíme, zjistíme, že je zbytečné porovnávat nejtěžší prvky na "dně" pole, protože jsou již na správném místě. Vlny si tedy můžeme dovolit postupně zkracovat o 1 prvek a tu poslední tedy dokonce úplně vypustit.

Dalším zlepšením může být kontrola, zda pole není již náhodou setříděné, protože to se může snadno třeba v polovině běhu cyklů stát a je potom zbytečné v třídění pokračovat. Můžeme si jednoduše nastavit proměnnou prohozeno na false a při každém prohození nastavit tuto proměnnou na true. Pokud nakonci zjistíme, že jsme nic neprohodili (proměnná má hodnotu false), máme hotovo. Tyto 2 zlepšení obsahuje ukázkový průběh a níže i zdrojový kód.

Vrcholnou variantou "bublacího" algoritmu je tzv. Bubble sort s přetřásáním (Shaker sort neboli Cocktail sort), kde v každém běhu vnitřního cyklu proběhnou 2 vlny - jedna zleva doprava, tlačící těžší prvky dolů, druhá zprava, vynášející lehčí prvky nahoru. Odstraňuje to problém tzv. zajíců a želv, kde zajíci jsou těžké prvky, které se rychle propadají dolů. V původní implementaci jdou však lehké prvky nahoru jen velmi pomalu.

Vlastnosti algoritmu

Časová složitost O (n2)
Stabilita Ano
Rychlost Velmi špatná

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.

Průběh

Protože Bubble sort je poněkud neoptimalizovaný algoritmus, bude průběh o něco delší, než bylo doposud zvykem.

Mějme pole následujících prvků:

3 2 5 1 9 4

První vlna projede celým polem a největší prvek "probublá" na konec.

3 2 5 1 9 4

Začneme tedy s vlnou a porovnáme první 2 prvky (3 a 2):

3 2 5 1 9 4

3 je jistě větší než 2, proto prvky prohodíme

2 3 5 1 9 4

Porovnáme další 2 prvky (3 a 5)

2 3 5 1 9 4

Ty jsou ve správném pořadí, takže je prohazovat nebudeme. Vlna pokračuje dále...

2 3 5 1 9 4
2 3 1 5 9 4
2 3 1 5 9 4
2 3 1 5 4 9

Po první vlně se maximum (9) opravdu probublalo na konec. Poslední prvek je tedy zatříděný a my si ho už nebudeme všímat. Další vlna bude o 1 prvek kratší, než předchozí, a vynese na konec maximum z nesetříděné části pole.

2 3 1 5 4 9
2 3 1 5 4 9
2 1 3 5 4 9
2 1 3 5 4 9
2 1 3 4 5 9

Po druhé vlně máme na konci již 2 setříděné prvky. Uděláme další vlnu.

2 1 3 4 5 9
1 2 3 4 5 9
1 2 3 4 5 9
1 2 3 4 5 9

Vidíme, že pole je nyní setříděné. Program by udělal ještě jednu vlnu a když by zjistil, že se nic neprohodilo, vrátil by výsledek.

Vizualizace

94
47
64
79
43
73
49
35
99
37
Pro spuštění vizualizace stiskni tlačítko Start nebo Krok.

Video ukázka

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
  • Klikni pro editaci
    • function bubbleSort(array &$list) {
        $j = count($list) - 2;
        // kontrola prohozeni
        $swapped = true;
        while ($swapped) {
          $swapped = false;
          for ($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--;
        }
      }
      
      
      • Zkontroluj, zda výstupy programu odpovídají předloze. S jinými texty testy neprojdou.

    • Public Sub Bubblesort(cisla() As Integer)
          Dim j As Integer = cisla.Length - 2
          Dim pomocna As Integer
          Dim prohozeno As Boolean = True ' kontrola prohození
          While prohozeno
              prohozeno = False
              For i As Integer = 0 To j
                  If cisla(i) > cisla(i + 1) Then ' prohození
                      pomocna = cisla(i)
                      cisla(i) = cisla(i + 1)
                      cisla(i + 1) = pomocna
                      prohozeno = True
                  End If
              Next
              j -= 1
          End While
      End Sub

    V další lekci, Insertion sort, si ukážeme algoritmus Insertion sort i se zdrojovými kódy.


     

    Jak se ti líbí článek?
    Před uložením hodnocení, popiš prosím autorovi, co je špatněZnaků 0 z 50-500
    Předchozí článek
    Selection sort
    Všechny články v sekci
    Třídicí/řadicí algoritmy
    Přeskočit článek
    (nedoporučujeme)
    Insertion sort
    Článek pro vás napsal David Hartinger
    Avatar
    Uživatelské hodnocení:
    177 hlasů
    David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
    Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
    Aktivity