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.

#include <bits/stdc++.h>
class count_sort
{
std::map<int, int> m;
std::map<int, int>::iterator it;
public:
void counting_sort(std::vector<int>& a){
for(int i=0; i<a.size(); i++)
{
m[a[i]]++;
}
}
void display()
{
it = m.begin();
while(it != m.end())
{
for(int i = 0; i < it->second; i++)
{
std::cout<<it->first<<" ";
}
it++;
}
std::cout<<"\n";
}
};
int main()
{
count_sort c1;
std::vector<int>v {2,5,3,0,2,3,0,3};
std::cout<<"The entered values are \n";
for(int i = 0; i < v.size(); i++)
{
std::cout<<v[i]<<" ";
}
std::cout<<"\n";
c1.counting_sort(v);
std::cout<<"The sorted values \n";
c1.display();
}





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



 Follow us on
                              

                                                                  
                                                                  
Reference:



You may also like:
C++: Insertion Sort using STL (Sorting)
C++: Implementation of Merge Sort
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

C++: Huffman Coding using STL

What is "namespace" and why do we use it?