Bublinkové třídění a zároveň třídění přetřásáním se dá shrnout pod označení "třídění přímou výměnou", neboť výměny prvku jsou jejich dominantním rysem. Podobně jako většina metod vnitřního třídění jsou tyto dvě metody jsou založeny na opakovaném procházení polem. Přitom se vždy porovnávají dva sousední prvky, a pokud nejsou uloženy ve správném pořadí, prohodí se.

Algoritmus bublinkového třídění (bubblesort) v nejjednodušší podobně můžeme vyjádřit následující pascalskou procedurou:

procedure Bublání;

var i,j: index;

      x: prvek;

begin

  for i := 2 to n do begin {n-1 krát projdeme polem}

    for j := n downto i do {průchod polem}

      if a[j-1].klíč > a[j].klíč then begin

        x := a[j-1]; {pokud prvky nejsou}

        a[j-1] := a[j];  {ve správném pořadí,}

        a[j] := x {prohodíme je}

      end

  end

end;{bublání}

Jestliže pole procházíme "odzadu", jako je tomu v proceduře Bublání, dostane se při prvním průchodu nejmenší prvek na první místo. Ve druhém průchodu už nemusíme procházet celé pole, stačí skončit na druhém místě, kam se při druhém průchodu dostane druhý nejmenší prvek; atd.

Příklad 4.1

Ukážeme si efekt procedury Bublání při třídění posloupnosti (44, 55, 12, 42, 9, 18, 6, 67). Na obrázku 4.1 jsme ji zapsali svisle ve sloupci nadepsaném Z. V dalších sloupcích vidíme tříděné pole při jednotlivých průchodech cyklem s parametrem i.

S trochou fantazie si můžeme představovat, že v prvním průchodu "vyplave" nejlehčí prvek na první místo (jako bublinka - odtud název), ve druhém průchodu druhý nejlehčí prvek atd.

Obr. 4. 1 Bublinkové třídění

Na první pohled je zřejmé, že algoritmus, popsaný procedurou Bublání, lze vylepšit. Tato procedura totiž nerozpozná utříděné pole, takže např. poslední tři průchody při třídění posloupnosti, uvedené v příkladu 4.1, byly naprosto zbytečné. To můžeme napravit např. tak, že budeme při každém průchodu zaznamenávat počet výměn. Jestliže nedojde k žádné výměně, je třídění skončeno. Cyklus for s parametrem i nahradíme cyklem repeat s podmínkou "v minulém průchodu došlo k alespoň jedné výměně".

Dalšího vylepšení můžeme dosáhnout tím , že si zapamatujeme i index prvku, kterého se poslední výměna týkala. Za tímto prvkem již nebyly žádné další výměny, takže prvky zde jsou již uspořádány, a proto tento úsek již příště nemusíme procházet.

Vedle toho je zřejmá nesymetrie algoritmu bublinkového třídění: na obrázku 4.1 je vidět, že nejmenší prvek (zde 6) "vybublá" na své místo ihned při prvním průchodu, i když byl původně na předposlední pozici, zatímco největší prvek (94) "klesá ke dnu" velmi pomalu, při každém průchodu jen o jednu pozici.

Analýza bublinkového třídění

Počet porovnání při bublinkovém třídění v nejjednodušší podobě nezávisí na uspořádání pole a je vždy roven

                                                                                            ( 1)

Minimální počet přesunů je zřejmě Mmin = 0, neboť pokud je pole již uspořádané, nebude nikdy splněna podmínka v příkazu if v proceduře Bublání.

Maximální počet přesunů dostaneme pro pole uspořádané obráceně. V tomto případě bude docházet k výměně prvků při každém porovnání v každém z průchodů; vezmeme-li v úvahu, že na jednu výměnu prvků potřebujeme 3 přesuny, dostaneme podobně jako ve vztahu (1)

                                                                                                    (2)

Průměrný počet přesunů bychom pak mohli odhadnout hodnotou

Poslední aktualizace: 29-05-2003.