Mastering Counting Sort: A Comprehensive Guide
Everything you need to know about counting sort at one place
What is Counting Sort?
Counting sort is a linear sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array (auxiliary is just a fancy word for helper), and then by iterating through this array the original array is sorted.
When to prefer Counting Sort?
Counting sort is preferred when the range of elements is smaller than the number of elements. In simple words, we could say that counting sort is preferred when many elements are repeated in the given array.
Pseudocode of Counting Sort
function countingSort(arr, n):
// Step 1: Find the maximum element in the array
maxElement = arr[0]
for i from 1 to n-1:
if arr[i] > maxElement:
maxElement = arr[i]
// Step 2: Create a count array with size maxElement + 1, initialized to 0
count = array of size (maxElement + 1) initialized to 0
// Step 3: Store the count of each element
for i from 0 to n-1:
count[arr[i]] = count[arr[i]] + 1
// Step 4: Store the sorted elements back into the original array
index = 0
for i from 0 to maxElement:
while count[i] > 0:
arr[index] = i
index = index + 1
count[i] = count[i] - 1
C++ Code for Counting Sort
void countingSort(int arr[], int n)
{
// Find the maximum element in the array
int maxElement = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] > maxElement)
{
maxElement = arr[i];
}
}
// Create a count array to store the count of each unique element
int *count = new int[maxElement + 1];
for (int i = 0; i < maxElement + 1; i++)
{
count[i] = 0;
}
// Store the count of each element
for (int i = 0; i < n; i++)
{
count[arr[i]]++;
}
// Store the sorted elements back into the original array
int index = 0;
for (int i = 0; i <= maxElement; i++)
{
while (count[i] > 0)
{
arr[index] = i;
index++;
count[i]--;
}
}
delete[] count;
}
Working of the code using an example
Let's assume we have the following array.
{2,4,6,2,5,6,2,5,7,2,4,3,2}
First, we find the maximum number in the array by iterating through the whole array and store it in a variable called
maxElement
which in this case is 7.Now we create a new array named
count
and initialize its size to maxElement + 1 to store the elements count from 0 tomaxElement
.(As the indexing starts from 0).We initialize the whole count array with 0 specifying that occurrence of each element at the moment is zero.
Then we iterate through the whole array using a for loop. The loop body says to go to the
arr[i]
which in first iteration is 2 so it goes to count[2] and increments its value from 0 to 1 and in this way the loop continues till the last element.The count array looks like this after we have iterated through the original array.
{0,0,5,1,2,2,2,1}
The count array shows that there are:
0 occurrences of 0.
0 occurrences of 1.
5 occurrences of 2.
1 occurrence of 3.
2 occurrences of 4.
2 occurrences of 5.
2 occurrences of 6.
1 occurrence of 7.
Now the final step is to iterate through the count array and sort the original array. For this we use a
for
loop and inside this for loop usingwhile
loop we specify the condition that implement the body only when the value in count array is greater than zero i.e. there is any occurrence of any element.Let me just also quickly explain the loop body. For the first iteration
count[i]
i.e.count[0]
is not greater than zero so it does nothing. Same forcount[1]
then forcount[2]
the value is 5 which is greater than zero so now what it does is it goes toarr[index]
(index is initialized to 0 before the start of loop) and places the value 2 inarr[0]
. Index is incremented by 1 andcount[i]
is decremented by 1 so now value of count[2] is 4 which is still greater than zero. It again places 2 in the original array tillcount[2]
becomes zero which means no more 2's are left. Then it goes tocount[3]
and follows this process. In this way the whole count array is iterated, and the original array is sorted.
Time complexity of counting sort
Time complexity of the above function is O(n+k)
where n is the number of elements and k is the range of elements.
Real life applications of counting sort
Counting sort is used where counting the frequencies of elements is required like in data analysis for creating histograms or frequency distribution of categorical data.
Counting sort can be used to handle large datasets where the elements fall within a small range.
Counting sort is often used as a subroutine in Radix sort which is another sorting algorithm.
Limitations of Counting sort
Counting sort works only for integers. It cannot be used for sorting of floating-point numbers.
Due to constraints Counting sort is not suitable for all types of data.
This post covers everything you need to know about Counting Sort. If you still have any queries, feel free to ask away—I’m more than happy to help. Your questions and thoughts are always appreciated. Don’t forget to follow this space for more informative tech blogs and updates.