Hey, Ninjas! One of the essential steps in preparation for interviews is learning sorting algorithms. Sorting is one of the crucial topics in data structure and algorithms. It is used to order the items specifically, and many other algorithms require sorting to function efficiently. There are many sorting algorithms like the bubble sort, quick sort, merge sort, counting sort, etc.
This blog will discuss counting sort working, implementation, and its examples. Before diving into the solution, let’s discuss the problem statement again.
Problem Statement
We are given an unsorted array containing non-negative elements. The main task is to sort the given array using the counting sort algorithm.
Input
Total Number of Elements (N) = 9
Array elements = [ 1, 3, 2, 3, 4, 6, 4, 1, 3 ]
Output
After applying the counting sort algorithm, our array looks like this-
Solution Approach
Counting sort is an integer sorting algorithm, which sorts elements in an array according to small positive integer keys. The method organizes an array by counting how many times each distinct array element appears. It is not a comparison-based algorithm as it doesn’t compare any two elements; instead, it hashes the value with their corresponding value and uses the position array to find the position of the current element in the sorted array.
Two operations that take place in the counting sort are as follows:
Count the number of unique elements in the array.
Determine each element's location or the index at which it will appear in the sorted array.
Algorithm
Find the input array's maximum element and store it in the variable ‘max_element.’
The ‘count’ array is declared with a size of (max_element - min_element + 1)and initialized with all elements' initial count being 0; the count is incremented every time the number at the index occurs in the array.
The ‘position’ array is declared and initialized with all elements' initial count being 0, which will store the position of each element in the sorted array.
The ‘position’ array is updated by taking the cumulative sums of the ‘count’ array.
The ‘count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
Elements are put into the sorted array using a for loop, and the function is finally called for sorting a given array.
Finally, the sorted array is displayed as the output and the input array to compare the two.
Dry Run
First, we need to store the count of all distinct elements in the initial array. For that, the maximum value in the array is stored in the variable ‘max_element’, and a new array of this length is created. (The size of the new array will be 6.)
Now with the length of the array being equal to the largest value stored, the count of the biggest element present in the initial array will be stored at the maximum index of the new array (the count of element ‘6’ in the initial array is stored at index 6 in the new array).
The ‘count’ array is updated according to the frequency of elements occurring in the initial array.
Our ‘count’ array looks like this-
However, we need to store each element's count and the last element's count to make the final sorted array.
This is stored in the ‘position array’ because the position of the next element depends on the number of times its previous element is repeated.
E.g - (There are two ‘1’s in the array, so after sorting, ‘2’ will be placed after two ‘1’s, i.e., the second index, and goes on).
To calculate the position of elements for the final sorted array, the value at each element's ‘position’ index is stored at the corresponding index as the sum of the number stored at the previous index.
For example, the position of the element ‘2’ will be 2 + 1 in the sorted array. Similarly, the position of element ‘3’ will be 3 + 3 in the final array.
Finally, we start with the last element of the initial array (3), go to that particular index (index 3) in the position array, and decrement the element at that index(6 is decremented to 5).
The resulting number (5) would be the index in the final array where the particular element will be placed.
After that, we have also decreased the position[3] value as the first 3 is placed, and then the next 3 is placed on the index = 4 and this process goes on till all the elements are placed.
Similarly, performing this operation for all indexes, our final sorted array looks like this-
Implementation in C++
#include <iostream>
#include <vector>
using namespace std;
// Function for performing counting sort
void counting_sort(vector <int> &arr){
// Array size
int N=arr.size();
int max_element = 0;
// Finding a maximum element of the array
for (int i = 0; i < N; i++){
max_element = max(max_element, arr[i]);
}
// Initialising the count array
vector <int> count(max_element+1,0);
for (int i = 0; i < N; i++){
count[arr[i]]++;
}
// Initialising the position array
vector <int>position(max_element+1,0);
// Changing the count array for positions
for (int i = 0; i <= max_element; i++){
position[i] = count[i];
if(i){
position[i] += position[i-1];
}
}
// Array for storing the final sorted array
vector <int> sorted (N);
for (int i = N - 1; i >= 0; i--){
position[arr[i]] -= 1;
sorted[position[arr[i]]] = arr[i];
}
for(int i = 0; i < N ;i++){
arr[i]=sorted[i];
}
}
int main(){
// The total number of elements in the array
int N = 9;
// Elements of the array
vector <int> arr = { 1, 3, 2, 3, 4, 6, 4, 1, 3 };
cout<<"Initial array \n";
for(auto i:arr){
cout<<i<<" ";
}
cout<<"\n\n";
// Calling counting sort the sort the array
counting_sort(arr);
cout<<"Array after sorting \n";
for(auto i:arr){
cout<<i<<" ";
}
return 0;
}
You can also try this code with Online C++ Compiler
public class MyClass {
// Function for performing counting sort
static void counting_sort(int arr[]){
// Array size
int N=arr.length;
int max_element = 0;
// Finding maximum element of the array
for (int i = 0; i < N; i++){
max_element = Math.max(max_element, arr[i]);
}
// Initialising the count array
int p=max_element+1;
int count[];
count = new int [p];
for (int i = 0; i <= max_element; i++){
count[i]=0;
}
// Storing count of each element
for (int i = 0; i < N; i++){
count[arr[i]]++;
}
// Initialising the position array
int position[];
position = new int [max_element+1];
for (int i = 0; i <= max_element; i++){
position[i]=0;
}
// Changing the count array for positions
for (int i = 0; i <= max_element; i++){
position[i] = count[i];
if(i>0){
position[i] += position[i-1];
}
}
// Array for storing the final sorted array
int sorted[];
sorted = new int [N];
for (int i = N - 1; i >= 0; i--){
position[arr[i]] -= 1;
sorted[position[arr[i]]] = arr[i];
}
for(int i = 0; i < N ;i++){
arr[i]=sorted[i];
}
}
// Driver Function
public static void main(String args[]) {
// Number of days
int N = 9;
// Declaration of prices vector
int arr[] = { 1, 3, 2, 3, 4, 6, 4, 1, 3 };
System.out.println("Initial Array");
for(int i = 0 ;i < N; i++){
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
System.out.println();
// Function call to perform counting sort
counting_sort(arr);
System.out.println("Final Sorted Array");
for(int i = 0 ;i < N; i++){
System.out.print(arr[i]);
System.out.print(" ");
}
}
}
You can also try this code with Online Java Compiler
The time complexity of the counting sort algorithm is O(N + K), ‘N’ being the number of elements in the array and ‘K’ being the range of elements in it.
Explanation: The count ‘K’ array is read on the output pass, and a new array is written with ‘N’ elements. So there are ‘N’ reads and K writes (to zero the counts), then ‘N’ writes and 'K' reads for (2 N + 2 K) operations, but since constant two is ignored, the time complexity comes out to be O (N + K).
Note: If the range of input values does not exceed the number of values to be sorted, counting sort is most effective.
Space Complexity
For an array with the maximum element being ‘K’ and ‘N’ being the size of the array, the space complexity is O(K + N) for counting sort.
Explanation: Two arrays of size N and K are declared corresponding to ‘sorted’ and ‘count’ & ‘position’ arrays which yield an overall space of O(N + 2*K) where we can ignore the constant 2, which forms O(N + K) space complexity.
Note: A larger range of elements gives larger space complexity. Therefore the Counting array is not ideal for a large range of integers.
Approach for Negative Elements
In the above-mentioned approach, the maximum number of the given elements is extracted and we initialize the count array according to the maximum element. In this approach, along with calculating the maximum element, we will also calculate the minimum number of the array and initialize the count array accordingly. We will shift the value of each element by a value equal to the minimum element of the array.
Input
Total Number of Elements (N) = 9
Array elements = [ -1, -3, 2, 3, 4, 6, 4, 1, 3 ]
Output
After applying the counting sort algorithm, our array looks like this-
[-3, -1, 1, 2, 3, 3, 4, 4, 6]
Explanation
While applying the counting sort algorithm, we will shift all the elements to the right by a value equal to the minimum element of the array. In the above example, the minimum element is equal to -3. Hence, all the elements will have the value as mentioned below:
-3 will have a value of 0 in the count array.
-1 will have a value of 2 in the count array.
1 will have a value of 4 in the count array.
2 will have a value of 5 in the count array.
3 will have a value of 6 in the count array.
4 will have a value of 7 in the count array.
6 will have a value of 9 in the count array.
We can observe that all the elements of the array are shifted towards the positive side by a value equal to the minimum element of the array.
Algorithm
Find the input array's maximum element and store it in the variable ‘max_element.’
Find the input array's minimum element and store it in the variable ‘min_element.’
The ‘count’ array is declared and initialized with all elements' initial count being 0; the count is incremented every time the number at the index occurs in the array.
The ‘position’ array is declared and initialized with all elements' initial count being 0, which will store the position of each element in the sorted array.
The ‘position’ array is updated by taking the cumulative sums of the ‘count’ array.
The ‘count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
Elements are put into the sorted array using a for loop, and the function is finally called for sorting a given array.
Finally, The sorted array is displayed as the output and the input array to compare the two.
Implementation in C++
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
// Function for performing counting sort
void counting_sort(vector <int> &arr){
// Array size
int N=arr.size();
int max_element = 0;
// Finding a maximum element of the array
for (int i = 0; i < N; i++){
max_element = max(max_element, arr[i]);
}
int min_element = INT_MAX;
// Finding a maximum element of the array
for(int i=0; i < N; i++){
min_element = min(min_element, arr[i]);
}
// Initialising the count array
vector <int> count(max_element - min_element + 1,0);
for (int i = 0; i < N; i++){
count[arr[i] - min_element]++;
}
// Initialising the position array
vector <int>position(max_element - min_element + 1,0);
// Changing the count array for positions
for (int i = 0; i <= max_element - min_element; i++){
position[i] = count[i];
if(i){
position[i] += position[i-1];
}
}
// Array for storing the final sorted array
vector <int> sorted (N);
for (int i = N - 1; i >= 0; i--){
position[arr[i] - min_element] -= 1;
sorted[position[arr[i] - min_element]] = arr[i];
}
for(int i = 0; i < N ;i++){
arr[i]=sorted[i];
}
}
int main(){
// The total number of elements in the array
int N = 9;
// Elements of the array
vector <int> arr = { -1, -3, 2, 3, 4, 6, 4, 1, 3 };
cout<<"Initial array \n";
for(auto i:arr){
cout<<i<<" ";
}
cout<<"\n\n";
// Calling counting sort the sort the array
counting_sort(arr);
cout<<"Array after sorting \n";
for(auto i:arr){
cout<<i<<" ";
}
return 0;
}
You can also try this code with Online C++ Compiler
public class MyClass {
// Function for performing counting sort
static void counting_sort(int arr[]){
// Array size
int N=arr.length;
int max_element = 0;
// Finding maximum element of the array
for (int i = 0; i < N; i++){
max_element = Math.max(max_element, arr[i]);
}
int min_element = Integer.MAX_VALUE;
// Finding a maximum element of the array
for(int i=0; i < N; i++){
min_element = Math.min(min_element, arr[i]);
}
// Initialising the count array
int p=max_element - min_element + 1;
int count[];
count = new int [p+1];
for (int i = 0; i <= p; i++){
count[i]=0;
}
// Storing count of each element
for (int i = 0; i < N; i++){
count[arr[i] - min_element]++;
}
// Initialising the position array
int position[];
position = new int [p+1];
for (int i = 0; i <= p; i++){
position[i]=0;
}
// Changing the count array for positions
for (int i = 0; i <= p; i++){
position[i] = count[i];
if(i>0){
position[i] += position[i-1];
}
}
// Array for storing the final sorted array
int sorted[];
sorted = new int [N];
for (int i = N - 1; i >= 0; i--){
position[arr[i] - min_element] -= 1;
sorted[position[arr[i] - min_element]] = arr[i];
}
for(int i = 0; i < N ;i++){
arr[i]=sorted[i];
}
}
// Driver Function
public static void main(String args[]) {
// Number of days
int N = 9;
// Declaration of prices vector
int arr[] = { -1, -3, 2, 3, 4, 6, 4, 1, 3 };
System.out.println("Initial Array");
for(int i = 0 ;i < N; i++){
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
System.out.println();
// Function call to perform counting sort
counting_sort(arr);
System.out.println("Final Sorted Array");
for(int i = 0 ;i < N; i++){
System.out.print(arr[i]);
System.out.print(" ");
}
}
}
You can also try this code with Online Java Compiler
The counting sort algorithm efficiently sorts arrays with non-negative integer keys, such as a list of positive integers, with keys just the value of the integer or a list of words having keys assigned to them by some scheme.
What is the disadvantage of counting sort?
The use of counting sort is only limited to arrays with integer elements because an array of frequencies cannot be constructed otherwise.
What is the difference between counting sort and bucket sort?
Bucket sort involves linked lists, dynamic arrays, or a large amount of pre-allocated memory, while count sort stores a single number, i.e., the count of items per bucket.
Which is the fastest sorting technique?
Quicksort is considered the quickest sorting algorithm because its time complexity is O( N log N) in the best and almost average case scenarios, and in the worst case, it goes up to O (N ^ 2). Thus, it has the upper hand in most cases.
Is counting sort better than quick sort?
Counting sort has better time complexity. However, it has worse space complexity. The better option depends on whether memory or CPU consumption is prioritized.
Moreover, counting sort might be computationally superior but can only be used for small integer values. Hence it cannot replace quicksort in all conditions.
Conclusion
Sorting algorithms are important as searching elements in a sorted array becomes easier than in an unsorted array. Overall, the time complexity of searching for an element is significantly reduced, which plays an essential role in programming. Some real-life applications of sorting algorithms are a contact list on your phone, a music playlist on your phone, and so on.
In this blog, we discussed the topic of the counting sort algorithm and the working of the algorithm. We also implemented the algorithm in two different languages C++ and Java. Sorting algorithms are also an essential topic in view of interview preparations and placement. It is, therefore, imperative to become an expert with sorting algorithms, understand what goes underneath the hood, and where you can apply your learnings.