Counting sort (ultra sort, math sort) je výkonný stabilní řadící algoritmus se složitostí , 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 , 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
Kód
/**
* 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;
}