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

view source
print?
01./**
02. * Counting sort
03. * @param array array to be sorted
04. * @return array sorted in ascending order
05. */
06.public static int[] countingSort(int[] array) {
07.    // array to be sorted in, this array is necessary
08.    // when we sort object datatypes, if we don't,
09.    // we can sort directly into the input array    
10.    int[] aux = new int[array.length];
11. 
12.    // find the smallest and the largest value
13.    int min = array[0];
14.    int max = array[0];
15.    for (int i = 1; i < array.length; i++) {
16.        if (array[i] < min) min = array[i];
17.        else if (array[i] > max) max = array[i];
18.    }
19. 
20.    // init array of frequencies
21.    int[] counts = new int[max - min + 1];
22. 
23.    // init the frequencies
24.    for (int i = 0;  i < array.length; i++) {
25.        counts[array[i] - min]++;
26.    }
27. 
28.    // recalculate the array - create the array of occurences
29.    counts[0]--;
30.    for (int i = 1; i < counts.length; i++) {
31.        counts[i] = counts[i] + counts[i-1];
32.    }
33. 
34.    // Sort the array right to the left
35.    // 1) look up in the array of occurences the last occurence of the given value
36.    // 2) place it into the sorted array
37.    // 3) decrement the index of the last occurence of the given value
38.    // 4) continue with the previous value of the input array (goto: 1), terminate if all values were already sorted
39.    for (int i = array.length - 1; i >= 0; i--) {
40.        aux[counts[array[i] - min]--] = array[i];
41.    }
42. 
43.    return aux;
44.}
view source
print?
01./**
02. * Counting sort
03. * @param array array to be sorted
04. * @return array sorted in ascending order
05. */
06.public static int[] CountingSort(int[] array)
07.{
08.    // array to be sorted in, this array is necessary
09.    // when we sort object datatypes, if we don't,
10.    // we can sort directly into the input array    
11.    int[] aux = new int[array.Length];
12. 
13.    // find the smallest and the largest value
14.    int min = array[0];
15.    int max = array[0];
16.    for (int i = 1; i < array.Length; i++)
17.    {
18.        if (array[i] < min) min = array[i];
19.        else if (array[i] > max) max = array[i];
20.    }
21. 
22.    // init array of frequencies
23.    int[] counts = new int[max - min + 1];
24. 
25.    // init the frequencies
26.    for (int i = 0; i < array.Length; i++)
27.    {
28.        counts[array[i] - min]++;
29.    }
30. 
31.    // recalculate the array - create the array of occurences
32.    counts[0]--;
33.    for (int i = 1; i < counts.Length; i++)
34.    {
35.        counts[i] = counts[i] + counts[i - 1];
36.    }
37. 
38.    // Sort the array right to the left
39.    // 1) look up in the array of occurences the last occurence of the given value
40.    // 2) place it into the sorted array
41.    // 3) decrement the index of the last occurence of the given value
42.    // 4) continue with the previous value of the input array (goto: 1), terminate if all values were already sorted
43.    for (int i = array.Length - 1; i >= 0; i--)
44.    {
45.        aux[counts[array[i] - min]--] = array[i];
46.    }
47. 
48.    return aux;
49.}







  1. Home
  2. Sorting algorithms
       
 

Place for your banner

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