Count Sort Algorithm

 Count Sort Algorithm

Count sort algorithm is yet another type of sorting algorithm. But when to use it so when the array or vector contains repeated elements with non floating values then the COUNT SORT ALGORITHM is used.

So below is the code for count sort algorithm with its TIME & SPACE COMPLEXITY.

Code:-

#include<iostream>

#include<vector>

using namesapce std;

void countSort(vector<int>&v){

int n=v.size();

//finding max element of the array

int max_ele=INT_MIN;

for(int i=0;i<n;i++){

max_ele=max(v[i],max_ele);

}

//finding frequency of the elements of the vector

vector<int>freq(n);

for(int i=0;i<n;i++){

freq[v[i]]++;

}

//finding cumulative frequency 

//cumulative frequency is the sum of number and its previous number 

//for ex ; v[i]+=v[i-1];

for(int i=1;i<=max_ele;i++){

freq[i]+=freq[i-1];

}

//sorting array

vector<int>ans(n);

for(int i=0;i<max_ele;i++){

ans[--freq[v[i]]]=v[i];

}

//putting elements into the original array

for(int i=0;i<n;i++){

v[i]=ans[i];

}

}

int main(){

int n;

cout<<"enter the size of the array"<<" "<<endl;

cin>>n;

vector<int>v(n);

//taking input values

for(int i=0;i<n;i++){

cin>>v[i];

}

countSort(v);

//printing output

for(int i=0;i<n;i++){

cout<<v[i]<<" ";

}

return 0;

}

OUTPUT:- enter the size of the array

6

5 4 3 2 3 2

2 2 3 3 4 5

This is the code with output of COUNT SORT algorithm.

Its TIME & SPACE COMPLEXITY is O(n+k) ,O(n+k)