Counting Sort

Counting Sort assumes that each of the  input element is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in O(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. For example, if there are 10 elements less than x, then x belongs in output position 11. This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don’t want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[], and thus length[A] =n. We require two other arrays: the array B[] holds the sorted output, and the array C[] provides temporary working storage.

 For more information on counting sort visit

Below is the C++ code for counting sort algorithm.

*Program to sort numbers using COUNTINGSORT
*inputs: N- number of integers to sort ,A-array of integers       
*output: sorted array of integers
*Assumption : all the number will lie in range 0 to MAX-1
*code tested on devc++ IDE
using namespace std;

void coutingsort(int A[],int len,int MAX)
{int *C=new int[MAX];
//intialise all elements to 0  
for(int i=0; i<len; i++)
for(int i=1; i<MAX; i++)   {   C[i]+=C[i-1];   } int *B=new int[len]; for(int j=len-1; j>=0; j--)
for(int j=len-1; j>=0; j--)
int N,MAX,temp;
int *A,*O;
int i,j;
cout<<"Enter the number of elements in array:\n"; cin>>N;
A=new int[N];
O=new int[N];
cout<<"Enter the upper limit for input values:\n"; cin>>MAX;
cout<<"Enter the array\n";
for(i=0;i<N;i++)   cin>>A[i];
cout<<"\nThe Sorted array after COUNTING SORT:"<<i<<"\n";  
//for more codes visit Code Library

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>