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.




1. #include <iostream>
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  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 visit


 Follow us on
                              
Reference:



You may also like:
C++ STL: Merge_Sort using Vector
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)

Popular Posts

Top 10 Web Sites Every Programmer Should Visit Daily

How do I improve my logical thinking and problem solving skills?

C++: STL Iterators