Counting sort (ultra sort, math sort) is an efficient sorting algorithm with asymptotic complexity O(n+k), which was devised by Harold Seward in 1954. As opposed to bubble sort and quicksort, counting sort is not comparison based, since it enumerates occurrences of contained values.

Description

Counting sort utilizes the knowledge of the smallest and the largest element in the array (structure). Using this information, it can create a helper array of frequencies of all discrete values in the main array and later recalculate it into the array of occurrences (for every value the array of occurrences contains an index of its last occurrence in a sorted array).

With this information the actual sorting is simple. Counting sort iterates over the main array and fills the appropriate values, whose positions are known thanks to the array of occurrences.

Advantages and disadvantages

The biggest advantage of counting sort is its complexity – O(n+k), where n is the size of the sorted array and k is the size of the helper array (range of distinct values).

It has also several disadvantages – if non-primitive (object) elements are sorted, another helper array is needed to store the sorted elements. Second and the major disadvantage is that counting sort can be used only to sort discrete values (for example integers), because otherwise the array of frequencies cannot be constructed.

Examples

Input array:          9 6 6 3 2 0 4 2 9 3 
Array of frequencies: 1 0 2 2 1 0 2 0 0 2 
Array of occurrences: 0 0 2 4 5 5 7 7 7 9 
Sorted array:         0 2 2 3 3 4 6 6 9 9  
Input array:          2 8 9 8 0 8 8 9 4 6 
Array of frequencies: 1 0 1 0 1 0 1 0 4 2 
Array of occurrences: 0 0 1 1 2 2 3 3 7 9 
Sorted array:         0 2 4 6 8 8 8 8 9 9  
Input array:          9 2 1 9 4 1 5 7 5 3 
Array of frequencies: 2 1 1 1 2 0 1 0 2  
Array of occurrences: 1 2 3 4 6 6 7 7 9 
Sorted array:         1 1 2 3 4 5 5 7 9 9  

Code

    /**
     * Counting sort
     * @param array array to be sorted
     * @return array sorted in ascending order
     */
    public static int[] countingSort(int[] array) {
        // array to be sorted in, this array is necessary
        // when we sort object datatypes, if we don't, 
        // we can sort directly into the input array     
        int[] aux = new int[array.length];

        // find the smallest and the largest value
        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];
        }

        // init array of frequencies
        int[] counts = new int[max - min + 1];

        // init the frequencies
        for (int i = 0;  i < array.length; i++) {
            counts[array[i] - min]++;
        }

        // recalculate the array - create the array of occurences
        counts[0]--;
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i-1];
        }

        // Sort the array right to the left
        // 1) look up in the array of occurences the last occurence of the given value
        // 2) place it into the sorted array
        // 3) decrement the index of the last occurence of the given value
        // 4) continue with the previous value of the input array (goto: 1), terminate if all values were already sorted
        for (int i = array.length - 1; i >= 0; i--) {
            aux[counts[array[i] - min]--] = array[i];
        }

        return aux;
    }
         /**
         * Counting sort
         * @param array array to be sorted
         * @return array sorted in ascending order
         */
        public static int[] CountingSort(int[] array)
        {
            // array to be sorted in, this array is necessary
            // when we sort object datatypes, if we don't, 
            // we can sort directly into the input array     
            int[] aux = new int[array.Length];

            // find the smallest and the largest value
            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];
            }

            // init array of frequencies
            int[] counts = new int[max - min + 1];

            // init the frequencies
            for (int i = 0; i < array.Length; i++)
            {
                counts[array[i] - min]++;
            }

            // recalculate the array - create the array of occurences
            counts[0]--;
            for (int i = 1; i < counts.Length; i++)
            {
                counts[i] = counts[i] + counts[i - 1];
            }

            // Sort the array right to the left
            // 1) look up in the array of occurences the last occurence of the given value
            // 2) place it into the sorted array
            // 3) decrement the index of the last occurence of the given value
            // 4) continue with the previous value of the input array (goto: 1), terminate if all values were already sorted
            for (int i = array.Length - 1; i >= 0; i--)
            {
                aux[counts[array[i] - min]--] = array[i];
            }

            return aux;
        }








       
 

Place for your banner

Here is the position ready for our customer's banners.