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 n je velikost řazeného pole a k 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;
         }
 







Doporučujeme