Given a collection of n items, each of which has a non-negative integer key whose maximum value is at most k, effectively sort it using counting sort algorithm.

Counting sort is an integer-based sorting algorithm for sorting an array whose keys lies between a specific range. It counts the number of elements that have each distinct key value and then use those counts to determine the positions of each key value in the output.

Counting sort can be used to find most frequent letter in a file or sort an limited range array efficiently. It is often used as a subroutine in radix sort sorting algorithm, and because of this, it is important for counting sort to be a stable sort.

### Algorithm:

The algorithm loops over the items, computing a histogram of the number of times each key occurs within the input collection. It then performs a prefix sum computation to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array. In below code:

- After the first for loop,
`freq[i]`

stores the number of items with key equal to i.

- After the second for loop, it instead stores the number of items with key less than i, which is the same as the first index at which an item with key i should be stored in the output array.

- Throughout the third loop,
`freq[i]`

always stores the next position in the output array into which an item with key i should be stored, so each item is moved into its correct position in the output array.

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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <stdio.h> #include <string.h> /* arr -- the input array of integers to be sorted n -- the length of the input array k -- a number such that all integers are in the range 0..k-1 */ void countSort(int arr[], int n, int k) { // create an integer array of size n to store sorted array int output[n]; // create an integer array of size k, initialized by all zero int freq[k]; memset(freq, 0, sizeof(freq)); // 1. using value of integer in the input array as index, // store count of each integer in freq[] array for (int i = 0; i < n; i++) freq[arr[i]]++; // 2. calculate the starting index for each integer int total = 0; for (int i = 0; i < k; i++) { int oldCount = freq[i]; freq[i] = total; total += oldCount; } // 3. copy to output array, preserving order of inputs with equal keys for (int i = 0; i < n; i++) { output[freq[arr[i]]] = arr[i]; freq[arr[i]]++; } // copy the output array back to the input array for (int i = 0; i < n; i++) arr[i] = output[i]; } // C program for stable version of counting sort int main() { int arr[] = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // range of array elements int k = 11; countSort(arr, n, k); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } |

`Output: `

1 1 2 2 4 4 10 10 10

Unlike other sorting algorithms like Insertion sort, Selection sort, Merge Sort, QuickSort, etc, Counting sort is not a comparison sort as it uses key values as indices into an array as evident from above code.

Below is the simpler version of counting sort that doesn’t produces a stable sort. i.e. the relative order of items with equal keys is not preserved anymore.

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 39 40 41 42 43 44 45 46 47 |
#include <stdio.h> #include <string.h> /* arr -- the input array of integers to be sorted n -- the length of the input array k -- a number such that all integers are in the range 0..k-1 */ void countSort(int arr[], int n, int k) { // create an integer array of size k to store count of each integer // in the input array int freq[k]; // initialize the integer array by 0 memset(freq, 0, sizeof(freq)); // using value of integer in the input array as index, // store count of each integer in freq[] array for (int i = 0; i < n; i++) freq[arr[i]]++; // overwrite the input array with sorted order int index = 0; for (int i = 0; i < k; i++) { while (freq[i]--) arr[index++] = i; } } // C program for counting sort int main() { int arr[] = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // specify range of array elements int k = 11; countSort(arr, n, k); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } |

`Output: `

1 1 2 2 4 4 10 10 10

### Performance:

The time complexity of counting sort is O(n + k) where k is the range of the input and n is the size of the input. Since it uses arrays of length k + 1 and n, the total space used by the algorithm is also

O(n + k). Counting sort can be highly space-efficient when range of keys k is significantly less than the number of items n, but when variation in keys is significantly greater than the number of items

k >> n, counting sort consumes a lot of space.

**Exercise:**

1. Extend the solution to handle negative integers.

2. Provide the exact range of keys by calculating the difference between the maximum and minimum key values.

**References:** https://en.wikipedia.org/wiki/Counting_sort

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply