Algorithms - Counting Sort

No sorting algorithm can sort n elements in better than O(n log n) time if comparing elements. However, there are other ways of sorting elements if we know some information about those elements in advance.

For example, assume that we are asked to sort n elements, but we are informed that each element is in the range of 0-k, where k is much smaller than n. We can take advantage of the situation to produce a linear - O(n) - sorting algorithm. That's Counting sort.

Counting sort (ultra sort or math sort) is a sorting algorithm which takes advantage of knowing the range (k) of the numbers in the array arr to be sorted. It uses this range to create an array of this length. Each index i in array B(ucket) is then used to count how many elements in arr have the value i; then counts stored in B can then be used to put the elements in arr into their right position in the resulting sorted array. The algorithm was created by Harold H. Seward in 1954.

C++ Code:

#include <iostream>

using namespace std;

void print(int a[], int sz) {
	for (int i = 0; i < sz;  i++ ) cout << a[i] << " ";
	cout << endl;
}

void CountingSort(int arr[], int sz) {
	int i, j, k;
	int idx = 0;
	int min, max;
 
	min = max = arr[0];
	for(i = 1; i < sz; i++) {
		min = (arr[i] < min) ? arr[i] : min;
		max = (arr[i] > max) ? arr[i] : max;
	}
 
	k = max - min + 1;
	/* creates k buckets */
	int *B = new int [k]; 
	for(i = 0; i < k; i++) B[i] = 0;

	for(i = 0; i < sz; i++) B[arr[i] - min]++;
	for(i = min; i <= max; i++) 
		for(j = 0; j < B[i - min]; j++) arr[idx++] = i;
 
	print(arr,sz);

	delete [] B;
}

int main()
{
	int a[] = {5,9,3,9,10,9,2,4,13,10};
	const size_t sz = sizeof(a)/sizeof(a[0]);
	print(a,sz);
	cout << "----------------------\n" ;
	CountingSort(a, sz);
}

Output is:

5 9 3 9 10 9 2 4 13 10
----------------------
2 3 4 5 9 9 9 10 10 13

Counting sort creates k buckets that store the number of times the k^th element was seen in the input array. It then makes two passes over the input array. During the first pass, it increments the count of the k^th bucket. In the second pass, it overwrites the original array by processing the count values in the total ordering provided by k buckets.