Tag Archives: counting sort code

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 http://www.algorithmist.com/index.php/Counting_sort

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

/*
 http://randomtechbits.in/
*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
*/
#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;

void coutingsort(int A[],int len,int MAX)
{int *C=new int[MAX];
//intialise all elements to 0  
memset(C,0,sizeof(int)*MAX);
for(int i=0; i<len; i++)
 {
 C[A[i]]+=1;
 }
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--)
  {
  B[C[A[j]]-1]=A[j];
  C[A[j]]-=1;
  }
for(int j=len-1; j>=0; j--)
  {
  A[j]=B[j];
  }
}
main()
{
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];
coutingsort(A,N,MAX);
cout<<"\nThe Sorted array after COUNTING SORT:"<<i<<"\n";  
for(i=0;i<N;i++)
  cout<<"\t"<<A[i];   
//for more codes visit Code Library
getch();
}