Bubble sort – bublinkové triedenie v Java

Triediace algoritmy sa používajú na vzostupné alebo zostupné preusporiadanie prvkov poľa alebo zoznamu podľa numerického alebo lexikografického poradia. Triedenie dát je veľmi dôležité pre optimálny výkon iných algoritmov, ktoré vyžadujú triedené vstupné dáta.

Existuje množstvo rozličných triediacich algoritmov. Výber vhodného algoritmu závisí na faktoroch ako veľkosť a vlastnosti vstupných dát, dostupná pamäť a požiadavky na časovú a priestorovú náročnosť.

Aby sme ti uľahčili výber, predstavíme si v našom seriáli postupne najznámejšie algoritmy triedenia dát, vysvetlíme si ich princípy, výhody a nevýhody a naprogramujeme si ich v Jave.

Dnes sa budeme venovať bublinkovému triedeniu (angl. bubble sort).

Bubble sort algoritmus

Bublinkové triedenie je algoritmus triedenia, ktorý porovnáva postupne každé dva susedné elementy a vymienia ich dovtedy pokiaľ nie sú zotriedené v požadovanom poradí. Algoritmus vyžaduje viacero iterácií.

Názov algoritmu je odvodený od vzduchových bublín, ktoré vo vode stúpajú na povrch. Analogicky v algoritme, elementy poľa prebublávajú v každej iterácií na koniec časti nezotriedeného poľa.

Bubble sort algoritmus – princíp fungovania

Predpokladajme, že chceme triediť elementy vo vzostupnom poradí. Ak má pole iba jeden element, tak sa považuje za zotriedené, inak je potrebné elementy zosortovať.

Prvá iterácia:

Porovnávajú sa postupne od začiatku poľa všetky dva susedné prvky poľa. Ak je prvý prvok väčší ako druhý, vymenia si poradie. Potom sa porovnávajú druhý prvok s tretím, tretí so štvrtým atď. Prvá iterácia končí porovnávaním posledných susedných prvkov.

Počas prvej iterácie sa vymieňaním prvkov zaručene dostane najväčší prvok poľa na koniec poľa.

Ostatné iterácie:

Posledný index poľa sa považuje za zotriedený, zvyšok poľa ešte zotriedený nie je. Pre nezotriedenú časť poľa sa opakuje postup z prvej iterácie. Každá iterácia prebuble najväčší prvok na koniec nezotriedeného poľa. Toto sa opakuje, až kým nie je pole zotriedené.

Počet iterácií: n-1
Počet porovnaní: n*(n-1)/2

Príklad

Máme nasledovné pole prvkov [3][1][2]. Zo vzorcov si vypočítame počet potrebných iterácií je 2 a počet porovnaní je 6.

V prvej iterácii prebehnú nasledujúce operácie: [1][3][2] -> [1][2][3]. Najväčší prvok 3 sa popresúval na posledný index poľa. Napriek tomu, že už je pole zotriedené vykoná sa ešte druhá iterácia, ktorá porovnáva prvé dva prvky poľa a keďže prvý a druhý prvok majú správne poradie, tak výmena ich poradia nenastane.

Optimalizovanie Bubble Sort algoritmu

Na vyššie zmienenom príklade sme videli, že ak už máme pole zotriedené, napriek tomu sa vykonávajú zbytočne ďalšie iterácie a porovnania. To samozrejme predlžuje čas behu algoritmu. Riešenie spočíva v tom, že pri každej iterácií si zaznamenáme, či nastala výmena poradia nejakých dvoch prvkov. Ak nie, tak považujeme pole za zotriedené a nasledovné iterácie už nevykonáme. Touto optimalizáciou znížime časovú náročnosť pre už zotriedené pole a zabezpečíme adaptabilitu algoritmu.

Výhody algoritmu Bubble sort

• Je ľahký na pochopenie aj implementáciu
• Nevyžaduje dodatočnú pamäť pri triedení
• Je stabilný, to znamená, že dva rovnaké prvky zo vstupu si zachovajú vo výsledku svoje relatívne poradie

Nevýhoda algoritmu Bubble sort

• Časová náročnosť je O(n²), čo z neho robí pomalý algoritmus pre veľkú sadu dát

Bubble sort časová náročnosť

Bubble sort animácie, vizualizácia, gif

Vizualizácia Bubble sort algoritmu vyzerá nasledovne:

Zdroj: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

Animáciu algoritmu nájdeš napríklad na stránke Toptal. Nachádza sa tam 8 typov algoritmov, animáciu si môžeš pustiť aj pozadu.

Na tejto stránke si môžeš prejsť jednotlivými krokmi algoritmu, vďaka čomu si vieš overiť časovú náročnosť algoritmu.

Bubble Sort Implementácia – príklad v Java

Poďme si naprogramovať optimalizovanú verziu bublinkového triedenia v Jave.

BubbleSort.java

package sorting;

// An optimized version of Bubble Sort
public class BubbleSort {
    private boolean change;
    private int temp;

    public void sort(int data[])
    {
        for (int i = 0; i < data.length - 1; i++) {
            System.out.println(i + 1 + ". iteration");
            change = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    change = true;
                    printArray(data);
                }
            }
            // If no two elements swapped, then end the sort method
            if (!change)
                return;
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.BubbleSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        BubbleSort bubbleSort = new BubbleSort();
        System.out.print("Input: ");
        bubbleSort.printArray(dataToSort);
        bubbleSort.sort(dataToSort);
        System.out.print("Sorted: ");
        bubbleSort.printArray(dataToSort);
    }
}

Výstup z tohto príkladu je:

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si BubbleSort kód v Java tu.

Ak si Java programátor a hľadáš prácu, pozri si naše benefity pre zamestnancov a reaguj na najnovšie ponuky práce.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.