Counting sort

Lecture

Counting sort (also called sorting by counting) — is a sorting algorithm that uses the range of numbers in the sorted array (list) to count matching elements. Using counting sort makes sense only when the numbers being sorted have (or can be mapped to) a range of possible values that is small compared to the set being sorted, for example, a million natural numbers less than 1000.

Assume that the input array consists of integers in the range from to , where . The algorithm will later be generalized to an arbitrary integer range. There are several modifications of counting sort; three linear ones and one quadratic one — which uses a different approach but shares the same name — are discussed below.

Simple algorithm

This is the simplest version of the algorithm. Create an auxiliary array C[0..k - 1] consisting of zeros, then sequentially read the elements of the input array A; for each A[i] increment C[A[i]] by one. Now it is enough to iterate over the array C, and for each {\displaystyle j\in \{0,...,k-1\}} Counting sort write the number j into the array A sequentially C[j] times.

SimpleCountingSort:
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

This is the same solution in C++.

void countingSort(int* array, int n, int k) {
	int c[k+1] = { 0 };
	for (int i = 0; i < n; i++) {
		c[array[i]] = c[array[i]] + 1;
	}
		
	int b = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < c[i]; j++) {
			array[b] = i;
			b = b + 1;
		}
	}	
}

Algorithm with a list

This variant (English: pigeonhole sorting, count sort) is used when the input is an array of data structures that must be sorted by keys (key). You need to create an auxiliary array C[0..k - 1]; each C[i] will later hold a list of elements from the input array. Then sequentially read the elements of the input array A, adding each A[i] to the list C[A[i].key]. Finally, iterate over the array C, and for each {\displaystyle j\in \{0,...,k-1\}} Counting sort write the elements of the list C[j] into the array A sequentially. The algorithm is stable.

ListCountingSort
    for i = 0 to k - 1
        C[i] = NULL;
    for i = 0 to n - 1
        C[A[i].key].add(A[i]);
    b = 0;
    for j = 0 to k - 1
        p = C[j];
        while p != NULL
            A[b] = p.data;
            p = p.next();
            b = b + 1;

Stable algorithm

In this variant, besides the input array A, two auxiliary arrays are needed — C[0..k - 1] for the counter and B[0..n - 1] for the sorted array. First, fill the array C with zeros, and for each A[i] increment C[A[i]] by 1. Next, the number of elements less than or equal to Counting sort is calculated. To do this, each C[j], starting from C , is increased by C[j - 1]. Thus, the last cell will hold the number of elements from to present in the input array. In the last step of the algorithm, the input array is read from the end, the value C[A[i]] is decreased by 1, and A[i] is written into each B[C[A[i]]]. The algorithm is stable.

StableCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    for j = 1 to k - 1
        C[j] = C[j] + C[j - 1];
    for i = n - 1 to 0
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];

Generalization to an arbitrary integer range

Several questions arise. What should be done if the range of values (min and max) is not known in advance? What should be done if the minimum value is greater than zero, or if the data being sorted contains negative numbers? The first question can be solved by a linear search for min and max, which does not affect the asymptotic complexity of the algorithm. The second question is somewhat more complex. If min is greater than zero, then when working with the array C, from A[i] subtract min, and add it back when writing the result. If there are negative numbers, when working with the array C, you need to add |min| to A[i], and subtract it back when writing the result.

Analysis

In the first two algorithms, the first two loops run in } Counting sort and }, respectively; the double loop runs in . In the third algorithm, the loops take , , and , respectively. In total, all three algorithms have linear time complexity . The memory used in the first two algorithms is , and in the third .

Quadratic counting sort algorithm

Counting sort is also the name given to a somewhat different algorithm. It uses the input array A and an auxiliary array B for the sorted set. In this algorithm, for each element of the input array A[i] you must count the number of elements less than it {\displaystyle c_{1}} and the number of elements equal to it but located earlier Counting sort ( ). Assign A[i] to B[c]. The algorithm is stable.

SquareCountingSort
    for i = 0 to n - 1
        c = 0;
        for j = 0 to i - 1
            if A[j] <= A[i]
                c = c + 1;
        for j = i + 1 to n - 1
            if A[j] < A[i]
                c = c + 1;
        B[c] = A[i];

Analysis

Obviously, the time estimate of the algorithm is Counting sort , and the memory is .

Implementation examples

Component Pascal[

Simple algorithm.

PROCEDURE CountingSort (VAR a: ARRAY OF INTEGER; min, max: INTEGER);
  VAR
    i, j, c: INTEGER;
    b: POINTER TO ARRAY OF INTEGER;
BEGIN
  ASSERT(min <= max);
  NEW(b, max - min + 1);
  FOR i := 0 TO LEN(a) - 1 DO INC(b[a[i] - min]) END;
  i := 0;
  FOR j := min TO max DO
    c := b[j - min];
    WHILE c > 0 DO
      a[i] := j; INC(i); DEC(c)
    END
  END
END CountingSort;

Implementation in PascalABC.Net

 1 const
 2   n = 5;
 3   m = 12; // Maximum value of all elements in a.
 4 
 5 var
 6   a: array [0..n] of integer;
 7   c: array [0..m] of integer; // Auxiliary array.
 8   i, j: integer; // Variables acting as indices.
 9   k:integer;
10 begin
11   for i := 0 to n do 
12     a[i] := Random(m); // Filling the array.
13   for i := 0 to m do
14     c[i] := 0;  //Zeroing the auxiliary array
15   for i := 0 to n do 
16     c[a[i]] := c[a[i]] + 1;
17   j := 0; // Zeroing j. Good programming style is to initialize all variables to zero, since not all compilers do this automatically.
18   for i := 0 to m do
19     for  k := 1 to c[i] do 
20     begin 
21         a[j] := i; 
22         Inc(j); 
23     end;
24   Writeln(a);
25 end.

Implementation in Python

 1 a=[]
 2 max_el=max(a)
 3 cnt=[0]*(max_el+1)
 4 
 5 for i in range(len(a)):
 6     cnt[a[i]]+=1
 7 
 8 pos=0
 9 for num in range(len(cnt)):
10     for i in range(cnt[num]):
11         a[pos]=num
12         pos+=1
13 print(a)

Sorting algorithms
Theory	Complexity Big O notation Order relation Sort types Stable In-place External
Exchange	Bubble sort , Cocktail shaker sort , Gnome sort, Quicksort, Comb sort , Odd-even sort , Radix sort
Selection	Selection sort , Heapsort, Smoothsort
Insertion	Insertion sort , Shell sort , Tree sort
Merge	Merge sort
Non-comparison	Counting sort , Bucket sort
Hybrid	Introsort, Timsort
Other	Topological sort , Sorting network, Bitonic sort
Impractical	Bogosort, Stooge sort , Pancake sort, slow sort