Counting Sort Algorithm – Idea to Implementation in C/C++

Counting Sort Featured Image

What is the counting sort algorithm? In Computer Science, sorting algorithms form the basis of many complex concepts and techniques. The task of arranging numbers or things in a specific order has really put mankind in deep thoughts.

In this article, we will be going through a specific sorting algorithm – Counting Sort. This algorithm works wonders when the range of numbers involved in sorting is restricted.

The Idea Behind Counting Sort

Before going to the nitty-gritty details of the algorithm, let us try to understand the idea behind this sorting technique.

Let us say that we have an array of size = 10 and we know that the highest number inside the array is 5. This restriction of the range provides us with the opportunity to count the frequency of every number between 0 to 5. We can basically create a fresh array using these frequencies.

This is the underlying concept of Counting Sort. Let us quickly move on to the algorithm.


Counting Sort Algorithm

We will do a step by step walk-through of the algorithm using an example array for a better understanding of the reader.

Counting Sort Input Array
Input Array

The numbers above the array values denote the index number.

Step 1: Find the maximum element

In order to find the range of numbers in the array, we need to find the maximum element in the array.

The best method to find the maximum element is by doing a linear traversal of the array, and keep on updating the maximum value till that point.

Counting Sort Max Element
Maximum element in input array

In the input array, we have max = 9 at index 8.

Time Complexity: O(n)

Space Complexity: O(1)


Step 2: Initialize a count array of length = (max + 1)

As we know our input array has a maximum value of 9, therefore, we know there are only 10 possible values 0 to 9. We need to create a count array with all possible values as indices and initialize each index with 0.

Counting Sort Count Array
Initializing Count Array

The next step must be to fill this count array.

Time Complexity: O(max)

Space Complexity: O(max)


Step 3: Fill the count array accordingly

In this step we have to fill the count array according to the frequencies present in the input array.

Counting Sort Fill Count Array
Filling Count Array

The values of Count Array have filled as per the frequencies of the index in the input array. For instance, there were three values of 5 in the input array, therefore the Count Array has value 3 at index 5.

Time Complexity: O(n)

Space Complexity: O(1)


Step 4: Calculate cumulative frequency in Count Array

We need to find the cumulative frequencies of the Count Array. This will come in handy later for sorting the input array.

Cumulative frequency is calculated by adding value at the current index with the value at the previous index.

Counting Sort Cumulative
Calculating cumulative frequency

It must be noted that the last value of the cumulative array must be total number of values present in the input array.

Note: To perform Counting Sort in descending order, we need to calculate cumulative frequencies in reverse order. Everything besides this remains the same.

Time Complexity: O(max)

Space Complexity: O(1)


Step 5: Fix the values in the sorted array

Using the cumulative count, we have somewhat the mapping for each element present in the input array to its position in the sorted array.

We will pop values from the start of the input array, and place them according to the value stored in the cumulative array.

Counting Sort Place Value Edited
How to place value in sorted array

After placing the first value, we need to decrement the corresponding value in the Cumulative array by 1. In this example, the value 7 in the cumulative array reduces to 6. The new cumulative array will be:

Counting Sort Cumulative Array
Updated Cumulative Array

Let us do one more iteration for this step for effective understanding. The next value in the input array is 2.

Counting Sort Place Next Value Edited
Placing 2 in the sorted array

As we can see, there is only one value less than 2 in the input array, that is 1. According to the situation of sorted array, there is only space left before 2, which makes absolute sense.

We must not forget to reduce the used value in the Cumulative array. The updated Cumulative Array will be:

Counting Sort Updated Cumulative
Updated Cumulative Array

Repeating this step for every value in the input array completes the algorithm for the Counting Sort.

Time Complexity: O(n)

Space Complexity: O(n)


Step 6: Printing the sorted array

The easiest part of the algorithm is printing the final sorted array.

Counting Sort Print Output
Print the sorted array

Time Complexity: O(n)

Space Complexity: O(1)


Overall Complexity of Counting Sort

Considering all the steps one by one, we have the following overall time and space complexities:

Overall Time Complexity: O(n + max)

Overall Space Complexity: O(n + max)


Implementation of Counting Sort in C++

#include<bits/stdc++.h>
using namespace std;

// Function implementing the Counting Sort
void counting_sort(int arr[], int n){

	// Step 1: Finding the maximum element
	int maximum = -1;

	for(int i=0;i<n;i++){
		maximum = max(arr[i], maximum);
	}

	// Step 2: Initialize a count array of length = (max + 1) 

	int count[maximum+1];
	memset(count, 0, sizeof(count));

	// Step 3: Fill the count array accordingly

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

	// Step 4: Calculate cumulative frequency in Count Array

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

	// Step 5: Fix the values in the sorted array

	int sorted_arr[n];

	for(int i=0;i<n;i++){
		sorted_arr[count[arr[i]]-1] = arr[i];
		count[arr[i]]--;
	}

	// Printing the sorted array

	for(int i=0;i<n;i++){
		cout<<sorted_arr[i]<<" ";
	}
	cout<<endl;
}

// The main function
int main(){

	// Initializing the array
	int arr[] = {5, 2, 5, 3, 6, 1, 5, 3, 9, 6};

	// Size of the array
 	int n = sizeof(arr)/sizeof(arr[0]);

 	// Function call to the sorting function
	counting_sort(arr, n);
	return 1;
}

Output:

1 2 3 3 5 5 5 6 6 9

Implementation of Counting Sort in C

#include<stdio.h>

// Function implementing the Counting Sort
void counting_sort(int arr[], int n){

	// Step 1: Finding the maximum element
	int maximum = -1;

	for(int i=0;i<n;i++){
		if(maximum < arr[i])
			maximum = arr[i];
	}

	// Step 2: Initialize a count array of length = (max + 1) 

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

	// Step 3: Fill the count array accordingly

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

	// Step 4: Calculate cumulative frequency in Count Array

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

	// Step 5: Fix the values in the sorted array

	int sorted_arr[n];

	for(int i=0;i<n;i++){
		sorted_arr[count[arr[i]]-1] = arr[i];
		count[arr[i]]--;
	}

	// Printing the sorted array

	for(int i=0;i<n;i++){
		printf("%d ", sorted_arr[i]);
	}
	printf("\n");
}

// The main function
int main(){

	// Initializing the array
	int arr[] = { 5, 2, 5, 3, 6, 1, 5, 3, 9, 6};

	// Size of the array
 	int n = sizeof(arr)/sizeof(arr[0]);

 	// Function call to the sorting function
	counting_sort(arr, n);
	return 1;
}

Output:

1 2 3 3 5 5 5 6 6 9

Advantages and Disadvantages of Counting Sort

Every concept in Computer Science has its pros and cons:

Advantages:

  • Linear Time Complexity. Since it is not a comparison-based sorting, it is not lower bounded by O(nlogn) complexity.
  • Reduced space complexity if the range of elements is narrow, that is, more frequency of close integers.

Disadvantages:

  • Both time and space complexities skyrocket if the range of input numbers is large.
  • It works only for discrete values like integers.
  • In case, negative integers are involved, the complexity increases, as well as certain changes in the algorithm, are required.

Conclusion

Sorting algorithms are a key component in the field of Computer Science. Being a non-comparison based sorting technique, Counting Sort is very efficient provided the range of values is limited.

We hope this article was understandable to you. For any queries related to the algorithm, feel free to comment below.

Comments

  1. Takish Ali says:

    Very well structured explanation.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages