Comb sort je řadicí algoritmus, který lze považovat za vylepšení bubble sortu. Ačkoliv má comb sort, stejně jako bubble sort, kvadratickou asymptotickou složitost , tak je díky eliminaci problému želv a zajíců v praxi rychlejší. Algoritmus vymyslel v roce 1980 Włodzimierz Dobosiewicz.

Princip

Comb sort, jak již bylo výše zmíněno, je vylepšením bubble sortu. Zopakujme si proto základní vlastnosti bublinkového řazení. Bubble sortu v každé své porovná první prvek s druhým a pokud jsou tyto v nesprávném pořadí (tj. těžší bublinka je blíže konci pole), tak prvky prohodí. Pak analogicky postupuje dál – porovná druhý prvek s třetím, třetí se čtvrtým a tak dále, dokud nezařadí nejlehčí nalezený prvek na konec řazené části pole. Po iteracích algoritmus terminuje – všechny prvky jsou seřazeny, jelikož poslední prvek musí být zařazen správně, jsou-li správně zařazeny prvky ostatní.

Problém želv a zajíců

Zásadním nedostatkem bubble sortu je problém želv a zajíců. Zatímco se aktuálně nejlehčí bublinka může přesunout při své iteraci ve směru řazení i přes celé pole (zajíc), tak se těžké bublinky hnou v každé iteraci maximálně o jednu pozici (želvy).

Comb sort

Comb sort, obdobně jako Shell sort (stejná myšlenka aplikovaná na insertion sortem) zavádí do řazení tzv. snižující se přírůstek. To znamená, že v každé iteraci jsou porovnávány prvky mezi nimiž je určitý přírůstek (mezera) – první prvek se čtvrtým, druhý s pátým, třetí se šestým a tak podobně. Přírůstek mezi prvky se s každou iterací postupně snižuje, dokud není jednotkový. Jednotkový přírůstek, který nastane při poslední iteraci comb sortu, značí, že dojde k jeho degradaci na prostý bubble sort – tj. jsou porovnávány sousední prvky. Díky tomuto jednoduchému triku se mohou v úvodních iteracích i těžké prvky – želvy – velmi rychle přesunout na správnou stranu pole.

Zásadní otázkou samozřejmě zůstává volba správné mezery. Bylo empiricky ukázáno, že velmi dobré výsledky dává mezera, která se vypočte postupným dělením délky pole číslem .

Vizualizace

Kód

    /**
     * Comb sort (od nejvyssiho)
     *
     * @param array pole k serazeni
     */
    public static void combSort(int[] array) {
        boolean swapped = false;
        int gap = array.length;
        while (gap != 1 || swapped) {
            gap /= 1.33;
            swapped = false;
            if (gap < 1) {
                gap = 1;
            }
            for (int i = 0; i + gap < array.length; i++) {
                if (array[i] < array[i + gap]) {
                    int tmp = array[i];
                    array[i] = array[i + gap];
                    array[i + gap] = tmp;
                    swapped = true;
                }
            }
        }
    }

/**
 * Comb sort (od nejvyssiho)
 *
 * @param array pole k serazeni
 */
function combSort(array) {
    var swapped = false;
    var gap = array.length;
    while (gap != 1 || swapped) {
        gap = Math.floor(gap / 1.33);
        swapped = false;
        if (gap < 1) {
            gap = 1;
        }
        for (var i = 0; i + gap < array.length; i++) {
            if (array[i] < array[i + gap]) {
                var tmp = array[i];
                array[i] = array[i + gap];
                array[i + gap] = tmp;
                swapped = true;
            }
        }
    }
}