Bublinkové triedenie

Triediace algoritmy usporiadajú prvky zoznamu do určitého poradia — napríklad od najmenšieho po najväčšie. Bublinkové triedenie je jedno z najjednoduchších — ideálne na pochopenie základného princípu triedenia.

Ako funguje?

Algoritmus opakovane prechádza zoznamom a porovnáva každý pár susedných prvkov. Ak je ľavý prvok väčší ako pravý, vymení ich. Väčšie prvky tak "bublajú" na koniec zoznamu — odtiaľ názov bublinkové.

Vizualizácia pre zoznam [5, 3, 8, 1]:

1. priechod:

• Porovnaj 5 a 3 → vymeň → [3, 5, 8, 1]
• Porovnaj 5 a 8 → nechaj → [3, 5, 8, 1]
• Porovnaj 8 a 1 → vymeň → [3, 5, 1, 8]

2. priechod:

• Porovnaj 3 a 5 → nechaj → [3, 5, 1, 8]
• Porovnaj 5 a 1 → vymeň → [3, 1, 5, 8]
• Porovnaj 5 a 8 → nechaj → [3, 1, 5, 8]

3. priechod:

• Porovnaj 3 a 1 → vymeň → [1, 3, 5, 8]
• Ostatné sú správne → hotovo!

Implementácia v Pythone

def bublinkove_triedenie(zoznam):
    n = len(zoznam)
    
    for i in range(n):
        # Každý priechod posuňuje ďalší najväčší prvok na miesto
        for j in range(0, n - i - 1):
            if zoznam[j] > zoznam[j + 1]:
                # Výmena susedných prvkov
                zoznam[j], zoznam[j + 1] = zoznam[j + 1], zoznam[j]
    
    return zoznam

cisla = [64, 34, 25, 12, 22, 11, 90]
print(bublinkove_triedenie(cisla))
# [11, 12, 22, 25, 34, 64, 90]

Optimalizácia — skoré ukončenie

Ak pri jednom priechode nedošlo k žiadnej výmene, zoznam je už zoradený a môžeme skončiť:

def bublinkove_triedenie_optimum(zoznam):
    n = len(zoznam)
    
    for i in range(n):
        vymena = False
        for j in range(0, n - i - 1):
            if zoznam[j] > zoznam[j + 1]:
                zoznam[j], zoznam[j + 1] = zoznam[j + 1], zoznam[j]
                vymena = True
        
        if not vymena:
            break   # žiadna výmena = zoznam je zoradený
    
    return zoznam

Výkon bublinkového triedenia

Kedy použiť bublinkové triedenie?

• Len na vzdelávacie účely — je ľahko pochopiteľné.
• Pre malé zoznamy (do ~20 prvkov) kde výkon nie je dôležitý.
• V produkcii ho nahraďte vstavanou funkciou sorted() alebo .sort().