Header Ads Widget

Program of Coutingsort

What is Counting sort:-

Before Implementing counting sort first we have to know what is counting sort . Counting sort is a non comparison based linear time sorting algorithm for cases where the input elements are in a limited range . it is a stable sorting algorithm . It is not an inplace sorting .

Algorithm:-

Step 1: First take a tem[] array of size k+1 (Max number in input array) and an ans[] array of size n (n is the size of the input array ) .

Step2: Initialize this array with 0.

Step 3: count the frequency of the elements of input array and store it in tem array.

Step 4: Find the Cumulative frequency of the element ( i.e tem[i] = tem[i]+tem[i-1] )

Step 5: Iterate over the input array from end to starting and insert the elements in the ans[] array on the basis of tem[] array as ( ans[tem[a[i]-1 ]=a[i] ).

Implementation of Counting sort:-

#include<stdio.h>

void CountingSort(int a[],int k,int n)
{
int b[n],c[k+1];
for(int i=0;i<=k;i++)
c[i]=0;
// couting the frequency of the elements
for(int i=0;i<n;i++)
c[a[i]]++;
// finding the cumulative frequency
for(int i=1;i<=k;i++)
c[i]=c[i]+c[i-1];
for(int i=n-1;i>=0;i--)
{
b[c[a[i]]-1]=a[i];
c[a[i]]-=1;
}
// updating the elements in the array
for(int i=0;i<n;i++)
a[i]=b[i];
}
int main()
{
int a[100],n,max=-1;
printf("Enter the number of elements in the array\n");
scanf("%d",&n);
printf("Enter the elements of the array\n");
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
// finding the max element
if(max<a[i])
max=a[i];
}
CountingSort(a,max,n);
printf("Sorted array is: \n");
for(int i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}

Output:-

Enter the number of elements in the array
5
Enter the elements of the array
1 6 3 2 7
Sorted array is:
1 2 3 6 7

 

Time Complexity :-

Time complexity of the counting sort is always depends of the number of elements in the input array and  elements also . So the time complexity of the Counting sort is :   O( n+k )   where k is maximum element in the input array

time complexity = O(n+k)

case 1: if k<n then O(n)

   case 2: if k>n then O(k)

Example : if there is an array a[1......n3] then what will be time complexity of counting sort algorithm. 

Solution : time complexity of the counting sort is O(n+k)

So O(n+n3) which is equals to O(n3).

 

 

 


Also check this:-

 
codechef problems:-

 

 

Wipro :-

 

 

Infytq :-

 

 

Key Points;-

Hackerrank:-

C-tutorial:-

 

See more:-