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 (n²)
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ů:

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

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

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

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

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

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.

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

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

{PHP}
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--;
  }
}


$list = [28, 3, 2, 18, 2, 17, 14, 8];
bubbleSort($list);
print_r($list);

{/PHP}

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.

Článek pro vás napsal David Hartinger

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

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity

Nejčastěji vyhledáváné