Counting sort (ultra sort, math sort) is an efficient sorting algorithm with asymptotic complexity , 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 – , where
is the size of the sorted array and
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;
}