Home » C++ programming language

Submitted by Shubham Singh Rajawat, on June 13, 2017

Learn: **Counting Sort in Data Structure using C++ Example**: Counting sort is used for small integers it is an algorithm with a complexity of O(n+k) as worst case.

**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 .

**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}

#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

Are you a blogger? Join our Blogging forum.

Comments and Discussions

We are using Google to publish ads on our website; Google has its own privacy policies. They may save log, cookies on your system. Google may also collect information of your system like IP address, region, city, country. For more details please go through the Google’s privacy policy.