Counting Sort in C – Algorithm and Program

Counting Sort

Counting sort is effective sorting algorithm when range is not greater than number of objects to be sorted. This sort can be used to sorting the negative input values.This sorting algorithm that sorts the data of an array by count the number of occurrences of each unique element in the array. 

Working of counting sort algorithm

Suppose the elements of array are –

1.Firstly, Find the maximum element from the given array. Suppose max be the maximum element.

2.Initialize array of length max + 1 having all zero elements. And this array used to store the count of the elements in the given array.

3. Now, we store the count of each array element at their corresponding index in array.

The count of an element stored as – Let array element ‘4’ is appeared two times, so the count of element 4 is 2. Hence, 2 is stored at the 4^th position of the count array. If any element is absent in the array, place 0, i.e. suppose element ‘3’ is absent in the array, so, 0 will be stored at 3^rd position.

Now, store cumulative sum of count array elements and it is used  to place the elements at the correct index of the sorted array.

The cumulative count of the count array is given below-

4. After that, find the index of each element of the original array

After placing element at their place, decrease its count by 1. Before placing element 2, its count was 2, but after placing it at right position, then new count for element 2 is 1.

Similarly, after sorting, the array elements are given as below

Now, the array is completely sorted.

Counting Sort Algorithm

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Program of counting sort in C

#include <stdio.h>

void countingSort(int array[], int size) {
  int output[10];

  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  int count[10];

  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

  // Copy the sorted elements 
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

// Function 
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(array) / sizeof(array[0]);
  countingSort(array, n);
  printArray(array, n);
}

Output

1  2  2  3  3  4  8  

Program of counting sort in C++

#include <iostream>
using namespace std;

void countSort(int array[], int size) {
  int output[10];
  int count[10];
  int max = array[0];

  // largest element of the array
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  // Initialize count array 
  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }


  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

  // Copy the sorted elements
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

// Function 
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}

// Driver code
int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(array) / sizeof(array[0]);
  countSort(array, n);
  printArray(array, n);
}

Output

1 2 2 3 3 4 8 

Use of Counting Sort

• There are smaller integers with multiple counts.
• Needed the linear complexity.

Read more, Merge sort