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
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.
}
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.
}