Q:

Counting Sort with C++ Example

0

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 .

 

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

Method Counting_Sort() contains three arguments A contains the elements entered by user, B array in which sorted elements are stored , n is the size of array A.

First of all we will have to initialize the array C with zero then we will store the frequency of elements in another array C i.e. if the value of an input element is x , we increment C[i](to store the occurrence of each number) then we will modify C[x] so that it will contain the last occurrence of the element x this can be done by storing the sum of C[x] and C[x-1] in C[x].
Now we will traverse the array A from last and find its position from C and that element in B at that address and at last we will modify C so that duplicate element will not end up in the same position in B.

Let us understand this with the help of an example:

Here , n=7 and A[]={0,1,5,7,8,6,3}

At first C[]={0,0,0,0,0,0,0,0,0}

Now we will modify C[]
C[]={1,1,0,1,0,1,1,1,1}

Now we will modify C[] so that it contains the last occurrence of any element 
x at C[x].

C[1]=C[0]+c[1] , C[2]=C[1]+C[2]… and so on
C[]={1,2,2,3,3,4,5,6,7}    /*Index of will start from zero*/

  Now we will store the sorted array in B[] by traversing A[] 
  and checking the position of that element from C[]

/*Index of A[] and B[] will start from one*/
So first A[7]=3  So the position of 3 in B[] is 3 and then we will update C[3]=2
Next A[6]=6 so the position of 6 in B[] is 5 and then we will update C[6]=4
And this will keep on going until we reach the first element then we will get 
our sorted array B[].
B[]={0,1,3,5,6,7,8}

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
12 345 89 100 23 0 18 44 111 1
0 1 12 18 23 44 89 100 111 345


Second Run:
Enter the size of the array :5
999 87 12 90 567
12 87 99 567 999    

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Implement shell sort using C++ program... >>
<< Find intersection of two linked lists using C++ pr...