In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.
For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0
2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7
The modified count array indicates the position of each object in
the output sequence.
3) Output each object from the input sequence followed by
decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.
/**
* @file counting_sort.cpp
* @author Huzaifa Arain (huzaifa.itgroup@gmail.com)
* @brief Implementation of counting sort algorithm
* @version 0.1
* @date 2019-10-02
*
* @copyright Copyright (c) 2019
*
*/
#include <bits/stdc++.h>
using namespace std;
/**
* @brief Helper function to print array
*
* @param A int type array
* @param n int type size of array
*/
void print_array(int A[],int n);
int main(int argc, char const *argv[])
{
int n = 18;
int IA[n] = {1,6,2,3,1,2,3,8,9,4,1,2,5,7,10,22,12,32};
cout<<"Input array ";
print_array(IA,n);
// Find the maximum value of arr
int max = 0;
for(int i = 0;i<n;i++){
if(IA[i] > max)
max = IA[i];
}
cout<<"Maximum value is "<<max<<endl;
int AuxSize = max + 1;
int Aux[AuxSize] = {};
cout<<"Auxiliary Array ";
print_array(Aux,AuxSize);
/* Count occurrences of elements repeated in Input Array and stored the
no of occurrences in the Auxiliary array such that index of Auxiliary array
is the element in Input Array and the value is the no of times its appeared in Input Array */
for (int i = 0; i < n;i++){
// Aux[IA[1]] means store the occurrences of 1 at index 1
// Aux[IA[i]] means store the occurrences of i at index i
Aux[IA[i]] = Aux[IA[i]] + 1;
}
cout<<"Auxiliary Array after counting occurrences ";
print_array(Aux,AuxSize);
/* Find the accumulative sum of Auxiliary array */
int AccumSum = 0;
for (int i = 0; i < AuxSize;i++){
AccumSum += Aux[i];
Aux[i] = AccumSum;
}
cout<<"Accumulative Sum of Auxiliary Array ";
print_array(Aux,AuxSize);
/* Create a new array same size of input array and place the values */
int OA[n] = {};
for (int i = n-1;i >= 0;i--){
OA[Aux[IA[i]]-1] = IA[i];
Aux[IA[i]] = Aux[IA[i]] - 1;
}
cout<<"Sorted Output Array ";
print_array(OA,n);
return 0;
}We are doing abstract level analysis that's why we are not interested in constants and are only interested in iterations.
for(int i = 0;i<n;i++){
if(IA[i] > max) // This will run n times
max = IA[i]; // This will run n times
}for (int i = 0; i < n;i++){
// Aux[IA[1]] means store the occurrences of 1 at index 1
// Aux[IA[i]] means store the occurrences of i at index i
Aux[IA[i]] = Aux[IA[i]] + 1; // This will run n times
}for (int i = 0; i < AuxSize;i++){
AccumSum += Aux[i]; // This will run k times
Aux[i] = AccumSum; // This will run k times
}for (int i = n-1;i >= 0;i--){
OA[Aux[IA[i]]-1] = IA[i]; // This will run n times
Aux[IA[i]] = Aux[IA[i]] - 1; // This will run n times
}T(n) = 3n + k as i said we are not interested in constants remove 3 and we left with
T(n) = n + k So the time complexity we get is Time Complexity: O(n+k)
and for the space we know that algorithm is creating an auxiliary array of size k and an output array of size n which gives us Space Complexity: O(n+k)
Hackerearth Counting Sort GeeksForGeeks Counting Sort TutorialsPoint Counting Sort