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.
Table of Contents
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.
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.
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.
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.
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.
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.
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:
Let us do one more iteration for this step for effective understanding. The next value in the input array is 2.
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:
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.
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.
Very well structured explanation.