### C++ STL :Implementation of Counting sort (Sorting)

I have studied this algorithm from Introduction to Algorithm.

**Counting sort**assumes that each of the n input elements is an integer in the range

0 to k, for some integer k means the maximum element in the array must be equal to k.

2. #include<vector>3. #include<algorithm>4.5. void counting_sort(std::vector<int>& a,std::vector<int>& b,int k){6. std::vector<int>c(k+1);7. for(int i=0;i<=k;i++) c[i]=0;8.9. for(int j=0;j<a.size();j++) c[a[j]]=c[a[j]]+1;//c[i] now contains the no. of elements equal to i10.11. for(int i=1;i<=k;i++) c[i]=c[i]+c[i-1]; //c[i] now contains the no. of elements less than or equal to i12.13. for(int j=a.size()-1;j>=0;j--){14. b[c[a[j]]]=a[j];15. c[a[j]]=c[a[j]]-1;16.}17. 18.}19. int main()20. {21. std::vector<int>v {2,5,3,0,2,3,0,3};22. std::vector<int>v1(v.size());23. int k;24. k=*std::max_element(v.begin(),v.end());25. counting_sort(v,v1,k);26. for(int i=0;i<=v.size();i++){27. std::cout<<v1[i]<<" ";28. }29.}
In line 14 we put the number in array such that to its right there are number greater than it and to its left less than or equal to it.

When k=O(n), the sort runs in

**$Θ(n)$****time.**
In line we have used

**std::max_element**which returns an iterator to the maximum element within a range.
To learn more about

**std::max_element**visitFollow us on

Reference:

**You may also like:**

**C++: Insertion Sort using STL (Sorting)**

**C++: Implementation of Queue using Array (Data Structure)**

**C++: Implementation of Heapsort**

**How do I learn competitive programming as a beginner?**

**C++: Stack implementation using LinkedList (Data Structure)**