Comb sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Comb sort je v informatice název relativně jednoduchého řadícího algoritmu, který vylepšuje algoritmus bubble sort. Comb sort původně navrhl Włodzimierz Dobosiewicz v roce 1980[1] a později byl opětovně objeven Stephenem Laceym a Richardem Boxem v roce 1991.[2] Časová náročnost je \Omega(n^2).[1]

Algoritmus[editovat | editovat zdroj]

Základní ideou Comb sortu je eliminace „želv“ (tj. malé hodnoty na konci seznamu), protože želvy v bubble sortu zpomalují proces řazení (způsobují mnoho výměn porovnávaných prvků). „Králíci“ (tj. velké hodnoty na začátku seznamu) nejsou v Comb sortu nijak řešeni, protože v bubble sortu nepředstavují problém.

V bubble sortu mají dva porovnávané elementy mezi sebou mezeru o velikosti jedna. Základní myšlenkou comb sortu je, že tato mezera může být volena podstatně vyšší než jedna (shell sort je také založen na této myšlence, ale je modifikací insertion sortu, spíše než bubble sortu).

Implementace[editovat | editovat zdroj]

Dále jsou uvedeny příklady zdrojového kódu v různých programovacích jazycích:

Příklad v pseudokódu[editovat | editovat zdroj]

function combsort(array input)
    gap := input.size //inicializace velikosti mezery
    shrink := 1.3 //nastavení mezery zmenšovacího faktoru

    loop until gap = 1 and swapped = false
        //aktualizace mezery pro další comb. Příklad níže
        gap := int(gap / shrink)
        if gap < 1
          //minimální mezera je 1
          gap := 1
        end if
        
i := 0 swapped := false //pro vysvětlení se podívejte na bubblesort
//jednotlivý "comb" přes vstupní seznam loop until i + gap >= input.size //podívejte se na shellsort na podobnou myšlenku if input[i] > input[i+gap] swap(input[i], input[i+gap]) swapped := true // Došlo k výměnně, takže seznam // není zaručeně seřazený end if i := i + 1 end loop
end loop end function

Příklad v jazyce C[editovat | editovat zdroj]

void comb_sort(int *input, size_t size) {
    const float shrink = 1.3f;
    int swap;
    size_t i, gap = size;
    bool swapped = false;
 
    while ((gap > 1) || swapped) {
        if (gap > 1) {
            gap = (size_t)((float)gap / shrink);
        }
 
        swapped = false;
 
        for (i = 0; gap + i < size; ++i) {
            if (input[i] - input[i + gap] > 0) {
                swap = input[i];
                input[i] = input[i + gap];
                input[i + gap] = swap;
                swapped = true;
            }
        }
    }
}

Odkaazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. a b Brejová, Bronislava. "Analyzing variants of Shellsort"
  2. "A Fast Easy Sort", Byte Magazine, April 1991

Související články[editovat | editovat zdroj]

  • Bubble sort, obvykle pomalejší algoritmus, který je základem Comb sortu.

Externí odkazy[editovat | editovat zdroj]