# Implementation of counting sort

**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 and is not an inplace sorting .

**Algorithm:-**

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

S**tep2**: Initialize this **tem[]** 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 index define by **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:-__

- Primary test
- Sum or difference
- point and line

__Wipro :-__

- Update the booking ID | Wipro previous year question paper solution
- Pages in PDF
- Find the location id
- Find the odd digits
- Find the Product ID

__Infytq :-__

__Key Points;-__

__Hackerrank:-__

- Python : missing characters : hackerrank solution
- Python : string transformation | Hackerrank solution
- Active Traders certification test problem | Hackerrank Solution
- Usernames changes certification test problem | Hackerrank Solution
- string Representation of objects certification test hackerrank solution
- Average Function | hackerrank certification problem solution

__C-tutorial:-__

- Micros in C
- Pointer in c
- Function declaration
- Types of user define function
- return type of function
- 2D array

__See more:-__

- c program to convert specified days into years weeks and days

- Print Reverse Hollow Pyramid
- Update the booking ID | Wipro previous year question paper
- Pages in PDF | Wipro previous year question paper
- Sparse Matrix in data structure
- Find the location ID | Wipro previous year Coding question
- find the odd digits | Wipro Coding question
- Find the product id | Wipro Coding question
- Difference between static and dynamic memory allocation
- What is asymptotic Notation