Counting sort is used for small integers it is an algorithm with a complexity of O(n+k) as worst case where ‘n’ is the number of elements and k is the greatest number among all the elements .

Counting sort program using C++
#include<iostream>
using namespace std;
int k=0;
/*Method to sort the array*/
void Counting_Sort(int A[],int B[],int n)
{
int C[k];
for(int i=0;i<k+1;i++)
{
/*It will initialize the C with zero*/
C[i]=0;
}
for(int j=1;j<=n;j++)
{
/*It will count the occurence of every element x in A
and increment it at position x in C*/
C[A[j]]++;
}
for(int i=1;i<=k;i++)
{
/*It will store the last
occurence of the element i */
C[i]+=C[i-1];
}
for(int j=n;j>=1;j--)
{
/*It will place the elements at their
respective index*/
B[C[A[j]]]=A[j];
/*It will help if an element occurs
more than one time*/
C[A[j]]=C[A[j]]-1;
}
}
int main()
{
int n;
cout<<"Enter the size of the array :";
cin>>n;
/*A stores the elements input by user */
/*B stores the sorted sequence of elements*/
int A[n],B[n];
for(int i=1;i<=n;i++)
{
cin>>A[i];
if(A[i]>k)
{
/*It will modify k if an element
occurs whose value is greater than k*/
k=A[i];
}
}
Counting_Sort(A,B,n);
/*It will print the sorted sequence on the
console*/
for(int i=1;i<=n;i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
return 0;
}
Output
First Run:
Enter the size of the array :10
11 344 89 100 23 0 18 44 101 1
0 1 11 18 23 44 89 100 101 344
Second Run:
Enter the size of the array :5
998 87 12 90 566
12 87 99 566 998
Types of Sorting Algorithms:
Additional Reading
- SEO Practices Everyone Should Follow SEO Rules
- Complete Top SEO Checklist
- Yoast Seo Premium 15.2 Nulled – WordPress SEO Plugin
- Top 50+ SEO Interview Questions
- What is a Backlink? How to Get More Backlinks
READ MORE
If you found this post useful, don’t forget to share this with your friends, and if you have any query feel free to comment it in the comment section.
Thank you 😊 Keep Learning !