Counting sort

Counting sort (ultra sort, math sort) je výkonný stabilní řadící algoritmus se složitostí O(n + k) , který vymyslel v roce 1954 Harold Seward. Counting sort nepracuje narozdíl od bubble sortu nebo quicksortu na principu porovnávání jednotlivých hodnot, ale na bázi výčtu jejich výskytů.

Princip

Counting sort využívá znalosti maximální a minimální řazené hodnoty . Díky může vytvořit pole četností hodnot (kolikrát je daná hodnota zastoupena v řazeném poli) a toto pole posléze přepočítat na pole posledních indexů (index i značí pozici posledního výskytu daného prvku v seřazeném poli).

Řazení probíhá jedním průchodem řazeného pole (zprava doleva) a ukládáním hodnot na správné místo v seřazeném poli (které známe díky poli indexů).

Výhody a nevýhody counting sortu

Výhodou counting sortu je jeho složitost O(n+k) , kde je velikost řazeného pole a je velikost pole indexů (rozsah různých hodnot).

První nevýhodou tohoto řadicího algoritmu je, že v případě řazení struktur potřebuje ke své práci nejen pomocné pole indexů, ale také dodatečné pole, do kterého budeme řadit. Druhým a významnějším nedostatkem pak je, že se counting sortem dají řadit pouze diskrétní hodnoty (tj. nelze s ním řadit například reálná čísla).

Příklady

 Vstupní pole:  9 6 6 3 2 0 4 2 9 3 
 Pole četností: 1 0 2 2 1 0 2 0 0 2 
 Pole výskytů:  0 0 2 4 5 5 7 7 7 9 
 Seřazené pole: 0 2 2 3 3 4 6 6 9 9

 Vstupní pole:  2 8 9 8 0 8 8 9 4 6 
 Pole četností: 1 0 1 0 1 0 1 0 4 2 
 Pole výskytů:  0 0 1 1 2 2 3 3 7 9 
 Seřazené pole: 0 2 4 6 8 8 8 8 9 9

 Vstupní pole:  9 2 1 9 4 1 5 7 5 3 
 Pole četností: 2 1 1 1 2 0 1 0 2  
 Pole výskytů:  1 2 3 4 6 6 7 7 9 
 Seřazené pole: 1 1 2 3 4 5 5 7 9 9

/**
 * Counting sort
 * @param array
 * @return pole serazene od nejnizsi honoty po nejvyssi
 */
public static int[] countingSort(int[] array) {
    // pole do ktereho budeme radit, v pripade primitiv nema smysl
    // da se radit i bez nej, ale v pripade objektu by to jinak neslo
    int[] aux = new int[array.length];
 
    // najdeme maximum a minimum
    int min = array[0];
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < min) min = array[i];
        else if (array[i] > max) max = array[i];
    }
 
    // vytvorime pole do ktereho budeme pocitat
    int[] counts = new int[max - min + 1];
 
    // zinicializujeme pocty vyskytu
    for (int i = 0;  i < array.length; i++) {
        counts[array[i] - min]++;
    }
 
    // prepocitame vyskyty na posledni index dane hodnoty
    counts[0]--;
    for (int i = 1; i < counts.length; i++) {
        counts[i] = counts[i] + counts[i-1];
    }
 
    // Serad pole zprava doleva
    // 1) vyhledej posledni vyskyt dane hodnoty v poli vyskutu
    // 2) uloz hodnotu na prislusne misto v serazenem poli
    // 3) sniz index posledniho vyskytu dane hodnoty
    // 4) pokracuj s predchozi hodnotou vstupniho pole (goto: 1), terminuj, pokud jiz vsechny hodnoty byly zarazeny       
    for (int i = array.length - 1; i >= 0; i--) {
        aux[counts[array[i] - min]--] = array[i];
    }
 
    return aux;
}

/**
 * Counting sort
 * @param array
 * @return pole serazene od nejnizsi honoty po nejvyssi
 */
public static int[] CountingSort(int[] array)
{
    // pole do ktereho budeme radit, v pripade primitiv nema smysl
    // da se radit i bez nej, ale v pripade objektu by to jinak neslo
    int[] aux = new int[array.Length];
 
    // najdeme maximum a minimum
    int min = array[0];
    int max = array[0];
    for (int i = 1; i < array.Length; i++)
    {
        if (array[i] < min) min = array[i];
        else if (array[i] > max) max = array[i];
    }
 
    // vytvorime pole do ktereho budeme pocitat
    int[] counts = new int[max - min + 1];
 
    // zinicializujeme pocty vyskytu
    for (int i = 0; i < array.Length; i++)
    {
        counts[array[i] - min]++;
    }
 
    // prepocitame vyskyty na posledni index dane hodnoty
    counts[0]--;
    for (int i = 1; i < counts.Length; i++)
    {
        counts[i] = counts[i] + counts[i - 1];
    }
 
    // Serad pole zprava doleva
    // 1) vyhledej posledni vyskyt dane hodnoty v poli vyskutu
    // 2) uloz hodnotu na prislusne misto v serazenem poli
    // 3) sniz index posledniho vyskytu dane hodnoty
    // 4) pokracuj s predchozi hodnotou vstupniho pole (goto: 1), terminuj, pokud jiz vsechny hodnoty byly zarazeny       
    for (int i = array.Length - 1; i >= 0; i--)
    {
        aux[counts[array[i] - min]--] = array[i];
    }
 
    return aux;
}

Princip

Výhody a nevýhody counting sortu

Příklady

Kód

Doporučujeme