Giudoku Official Site
Counting sort

Counting sort is a very fast sorting algorithm. Unfortunately it can't be always used because of the initial conditions needed.
Input: A[1...n] with the assumption that 0 <= A[i] <= k for a certain k. If k is too large, the algorithm becomes inefficient in terms either of running time or of memory usage.
Output: B[1...n] sorted.

The counting sort has 4 main steps.
1) Init: the C and B arrays are created, the first of k elements, the second with n elements as we said above. All the elements must be zero.
2) First for loop: we count the occurrence of each value in A, such that C[i] contains the number of occurrences of i in A.
3) Second loop: we sum two-by-two the occurrences. Now each C[i] contains the number of elements in A that are lesser than or equal to i (you can verify by hands how it works, it's pretty easy). Observation: the value i will go in the cell number C[i] or less in the final array.
4) Final loop, distribution step: taking the previous observation, we distribute the elements in the brand new B.

It's easy to see from the code than the running time is O(k+n). In particular, the algorithm stays efficient until k < nlogn.
Counting sort has another property, which it's called stability: the relative order of equal elements is mantained during the sorting. This can seem just a curiosity, but it's useful for another sorting algorithm, radix sort.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.Arrays;

public class CountingSort
{
	public static void main(String[] args)
	{
		int[] v1 = {4, 1, 8, 2, 7, 5, 6, 3, 9, 0};

		System.out.println("Before sorting: " + Arrays.toString(v1));
		System.out.println("After sorting: " + Arrays.toString(counting(v1)));
	}

	public static int[] counting(int[] A)
	{
		int k = 10;
		int[] C = new int[k];
		int[] B = new int[A.length];

		for (int j = 0; j < A.length; j++)
		{
			(C[A[j]])++;
		}

		for (int j = 2; j < k; j++)
		{
			C[j] = C[j] + C[j-1];
		}

		for (int j = A.length-1; j>=0; j--)
		{
			B[C[A[j]]] = A[j];
			C[A[j]]--;
		}

		return B;
	}
}