Comb sort – hrebeňové 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 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ť hrebeňovému triedeniu (angl. comb sort).

Comb sort algoritmus

Hrebeňové triedenie je algoritmus triedenia, ktorý vymyslel poľský informatik Włodzimierz Dobosiewicz a jeho cieľom bolo vylepšiť algoritmy triedenia založené na metóde výmeny prvkov. Ak si čítal náš článok o Bubble sort (bublinkovom triedení), tak už vieš, že jeho najväčší nedostatok spočíva v tom, že existujú scenáre pri triedení prvkov, ktoré nie sú pre daný algoritmus vhodné.

Napr. pri vzostupnom triedení sú problematické malé elementy, ktoré sa nachádzajú na konci poľa a pri zostupnom triedení veľké elementy, ktoré sa nachádzajú na začiatku poľa, pretože trvá pomerne veľa iterácií kým sa daný prvok pri triedení popresúva na svoje miesto. Comb sort to rieši tak, že na začiatku triedenia sa zameriava práve na takéto problematické prvky a tie sa prednostne vymieňajú.

Comb sort algoritmus – princíp fungovania

Základná myšlienka comb sortu spočíva v tom, že rýchlo eliminuje malé hodnoty blízko konca zoznamu (tzv. korytnačky), pretože v bublinovom triedení to triedenie výrazne spomaľuje a to použitím medzery (alebo hrebeňa), ktorá sa postupne zmenšuje. Veľké hodnoty okolo začiatku zoznamu, nepredstavujú problém v bublinovom/hrebeňovom triedení.

Keď sa porovnávajú akékoľvek dva prvky v bublinovom triedení majú vždy medzeru (vzdialenosť od seba) 1. Základnou myšlienkou hrebeňového triedenia je, že medzera môže byť oveľa väčšia ako 1 a vôbec to nemusí byť fixná konštanta a môže sa po iteráciách meniť.

Medzera začína s veľkou hodnotou, zvyčajne rovnakou ako dĺžka triedeného poľa, a potom sa zmenšuje o určitý faktor (zvyčajne okolo 1.3). Tento proces sa opakuje, kým medzera nedosiahne hodnotu 1, vtedy sa algoritmus správa ako bežné bublinkové triedenie, ale v tomto okamihu je pole už čiastočne usporiadané, čo robí finálnu iteráciu efektívnejšou. Experimentálne sa zistilo, že príliš malá hodnota medzery spomaľuje algoritmus tým, že robí zbytočne veľa porovnaní, zatiaľ čo príliš veľká hodnota medzery sa nedokáže efektívne vysporiadať s korytnačkami, takže si vyžaduje veľa prechodov s medzerou 1.

Výhody algoritmu Comb sort:

• je ľahký na pochopenie aj implementáciu,
• nevyžaduje dodatočnú pamäť pri triedení,
• rieši problém malých hodnôt na konci zoznamu,
• v priemere je rýchlejší ako Bubble sort.

Nevýhoda algoritmu Comb sort:

• časová náročnosť je však stále O(n²), čo z neho robí pomalý algoritmus pre veľkú sadu dát,
• nie je stabilný.

Comb sort časová náročnosť

Comb sort animácie, vizualizácia, gif

Vizualizácia Comb sort algoritmu vyzerá nasledovne:

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

Animáciu algoritmu Comb sort nájdeš napríklad na tejto stránke.

Comb Sort Implementácia  – príklad v Java

Poďme si naprogramovať tento algoritmus s dynamickou medzerou v Jave.

CombSort.java

package sorting;

public class CombSort {
    private boolean change;
    private int temp;
    private int gap;

    public void sort(int data[])
    {
        change = false;
        // gap init
        gap = data.length;
        int i = 0;
        while (gap != 1 || change) {
            change = false;
            // calculate new gap
            gap /= 1.33;
            if(gap <= 1)
                gap = 1;
            System.out.println(++i + ". iteration (gap = " + gap + ")");
            for (int j = 0; j + gap < data.length; j++) {
                if (data[j] > data[j + gap]) {
                    temp = data[j];
                    data[j] = data[j + gap];
                    data[j + gap] = 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.CombSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        CombSort combSort = new CombSort();
        System.out.print("Input: ");
        combSort.printArray(dataToSort);
        combSort.sort(dataToSort);
        System.out.print("Sorted: ");
        combSort.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 Comb Sort kód v Java.

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.