IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
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 si ukázali algoritmus Selection sort i se zdrojovými kódy.

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

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
  • 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--;
      }
    }
    
    
  • 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.


 

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í:
140 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