Counting Sort

  1. Counting Sort Algorithm
  2. Counting Sort Example
  3. Counting Sort Algorithm Implementation
  4. Counting Sort Algorithm Complexity

Counting sort is a non-comparative sorting algorithm. It sorts an array by counting occurrences of each unique element. It partially hashes the count of unique elements and then performs calculations to find the index of each element in the final, sorted array. It is quite a fast algorithm but unsuitable for large datasets. It is used as a subroutine inside radix sort.

Counting Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

  • Find out the maximum element max and minimum element min inside the array.
  • Initialize an array count of length max-min+1 with all elements set to 0.
  • Initialize an array output of size same as the input array A.
  • Store the count of all elements inside the count array by subtracting min and using the difference as the index.
  • Cumulate the sum of elements inside the count array. The count array now holds the position of each element in the sorted array.
  • Starting from the end take elements from A and do the following:
  • Compute elements index as count[A[i]-min]-1 and store A[i] in output.
  • decrease count[A[i]-min] by 1.
  • Store the output elements back to original array A.

Counting Sort Example

Suppose we have the array: (6, 3, 2, 7, 4, 5, 4, 2). We will sort it using the counting sort algorithm.

  • maxm = 7
  • minm = 2
  • range = 6
  • count and output are initialized with zeros.
index 0 1 2 3 4 5
value 0 0 0 0 0 0
  • count array after computing the count of all the elements.
index 0 1 2 3 4 5
value 2 1 2 1 1 1
  • count array after cumulation of the sum of elements.
index 0 1 2 3 4 5
value 2 3 5 6 7 8
  • First Iteration: A[7]=2
count 1 3 5 6 7 8
output 0 2 0 0 0 0 0 0
  • Second Iteration: A[6]=4
count 1 3 4 6 7 8
output 0 2 0 0 4 0 0 0
  • Third Iteration: A[5]=5
count 1 3 4 5 7 8
output 0 2 0 0 4 5 0 0
  • Fourth Iteration: A[4]=4
count 1 3 3 5 7 8
output 0 2 0 4 4 5 0 0
  • Fifth Iteration: A[3]=7
count 1 3 3 5 7 7
output 0 2 0 4 4 5 0 7
  • Sixth Iteration: A[2]=2
count 0 3 3 5 7 7
output 2 2 0 4 4 5 0 7
  • Seventh Iteration: A[1]=3
count 0 2 3 5 7 7
output 2 2 3 4 4 5 0 7
  • Eighth Iteration: A[0]=6
count 0 2 3 5 6 7
output 2 2 3 4 4 5 6 7

Finally, we store the output array inside A and get the sorted array - 2, 2, 3, 4, 4, 5, 6, 7.

Counting Sort Algorithm Implementation

#include<iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

int minm(int arr[], int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    return min;
}

void countingSort(int arr[], int n) {
    int min = minm(arr, n);
    int max = maxm(arr, n);
    int range = max - min + 1;
    int count[range]={};
    int output[n];
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;

    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

int main() {

    int n = 7;
    int arr[7] = {3, 5, 1, 1, 4, 2, 1};
    cout << "Input arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    countingSort(arr, n); // Sort elements in ascending order
    cout << "Output arr: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

This implementation also works for negative numbers.

Counting Sort Algorithm Complexity

Time Complexity

  • Average Case

Counting Sort iterates through all the n items twice and iterates through the count array once. So, it has a time complexity of O(n + b) where b is the range of input. Since b is often small, the counting sort’s time complexity is said to be of the order of [Big Theta]: O(n).

  • Worst Case

The worst-case time complexity is [Big O]: O(n).

  • Best Case

The best-case time complexity is [Big Omega]: O(n). It is the same as the worst-case time complexity.

Space Complexity

Space Complexity for the counting sort algorithm is O(n+b), where b is the range of input. It comes from count &output arrays. Sometimes b can be larger than n, but if b is small, the time complexity is said to be of O(n).

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Binary Sort
  • Radix Sort