C or C++ Program for Counting Sort

This article describes about the program for counting sort in C/C++. Let us discuss about the counting sort.

What is Counting Sort?
Counting sort is a sorting technique based on keys between specific ranges. It works by counting the number of objects having distinct key values. It performs some arithmetic operation and calculates the position of each object in the output sequence.
It works by counting the occurrences of each data value. It imagines that there are n data items in the range of 1…m (m is an integer). For each input element the algorithm can then determine, the amount of elements less than it. For example if there are 8 elements less than element x, then x belongs in the 9th data position.

Counting Sort Program

#includea
#include
#include

find_k(int a[],int n) {
     int hight=a[1];
     for(int i=2;i<=n;i++)
     if(hight<a[i])
     hight=a[i];
     return hight;
     }

void counting_sort(int a[],int b[],int n) {
     int c[300];
     int k=find_k(a,n);
     for(int i=0;i<=k;i++)
    c[i]=0;
     for(int j=1;j<=n;j++)
	c[a[j]]=c[a[j]]+1;
     for(i=1;i<=k;i++) 	c[i]=c[i]+c[i-1];      for(j=n;j>=1;j--) {
	b[c[a[j]]]=a[j];
	c[a[j]]=c[a[j]]-1;
	}
}

void main() {
clrscr();
int a[34],b[23],n;

     cout<<"     \" This will arrange data in ascending order (using counting sort) .\""<<endl<<endl;
     cout<<"How many number ?. give a integer number."<<endl;      cin>>n;
     cout<<"What are the elements ?. Give the numbers."<<endl;

     for(int i=1;i<=n;i++) 	cin>>a[i];

     cout<<endl;
     cout<<"You have given the following numbers :"<<endl;
     for(i=1;i<=n;i++)
	cout<<a[i]<<"  ";

     counting_sort(a,b,n);
     cout<<endl;
     cout<<"After sorting the values are.......\n";
     for(i=1;i<=n;i++)
	cout<<b[i]<<"  ";

getch();
}