# Implementation of Counting Sort using C++ [duplicate]

Please review my code. If any improvement needed please point out. I have used std::map. Is there any better alternative?

#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();
}


• "It says add more details". What is "It"? – Justin Aug 14 '17 at 18:36
• Error Message in StackOverflow – coder Aug 14 '17 at 18:50
• Are you saying that when you were posting this, it said "add more details", so you typed that text and the error went away? – Justin Aug 14 '17 at 18:52
• If I will add more details the question become messy. – coder Aug 14 '17 at 18:57
• Okay. What that error message means is that you have a bunch of code and little non-code text. In your case, it seems like it's probably fine, but by "add more details", it was asking you to add more extra text, such as a brief explanation of what counting-sort is, or a couple more things that you wanted to emphasize in the reviews. – Justin Aug 14 '17 at 18:59

#include <bits/stdc++.h>


You normally shouldn't use this. It includes every standard library header. If you compile without precompiled headers, this would make your compilation time much greater. The recommended practice is to #include just what you need, and if you want to use a precompiled header as well, that's just fine.

class count_sort
{


It is a bit strange to use a class for sorting. That your sort function is in a class implies that there's state, which is unexpected. You could use a namespace.

  std::map<int, int> m;
std::map<int, int>::iterator it;


This state can easily be moved inside the functions, to the smallest scope possible.

  void counting_sort(std::vector<int>& a){


The name counting_sort is a bit redundant, seeing as it's a member function of a class called count_sort. You could use sort, or even operator(). Other than that, by taking std::vector<int>& as a parameter, you make this sort function not very general. The way the parameters are usually taken for a sort function (in C++) is as an iterator range:

template <typename Iter>
void counting_sort(Iter begin, Iter end) {


If you don't want to use templates, that's fine, but keep in mind that they make it more general.

One other thing to note is that you never change the vector in this function. That's a sign that it should be taken by const& rather than &. However, the expected semantics of a function called sort is that it modifies its parameter so that, after the function is called, the parameter is sorted. It's unusual and unexpected to have to call another function to obtain the output.

For the actual implementation, you can make use of C++11's range-based for loops (aka for-each loops). This:

for(int i=0; i<a.size(); i++)
{
m[a[i]]++;
}


Becomes this:

// Read as "for each int i in a, ..."
for (int i : a) {
m[i]++;
}


Putting together my suggestions, without templates, would look something like this:

namespace counting_sort {
void sort(std::vector<int>& vec) {
std::map<int, int> count;

for (int i : vec) {
++count[i];
}

// modify the parameter; write the values back out
auto begin = vec.begin();
for (const auto& pair : count) {
while (pair->second > 0) {
*begin = pair->first;
++begin;
--pair->second;
}
}
}
}

1. One class should have one focused responsibility. Your class sorts the vector and prints the result. These operations are unrelated.

2. There'so no need to have a class at all. It doesn't represent any entity. It's just a function, like std::sort. The map can be local variable.

3. To keep it more similar to the standard library, I'd recommend to take two forward iterators instead of a vector. It'll be more flexible this way.
• +1 for suggesting not to limit the input to std::vector's. – einpoklum Aug 14 '17 at 19:53

My suggestions:

## Don't write this.

It's unlikely you can't find a reasonable bucket-based/counting-based sort already implemented in C++. Don't reinvent the wheel.

... but assuming you are writing this:

## Templatize

You're only sorting integers; why? If you had some super-nifty hand-coded assembly that only works for ints, then fine; but you don't. So templatize - over the data type, and over the iterator type (i.e. don't take a vector, take start & end iterators, like std::sort()

## You're going to be very slow I

std::map is super-slow. std::unordered_map is still very slow. If you're using a map, choose a better one.

## You're going to be very slow II

Your code is single-threaded and doesn't use SIMD. You might get free SIMD from the compiler - but I wouldn't bet on it, and you have to check the compiled code (after you've gotten rid of std::map).

## Why a counting sort?

You've not given any reason why you need a counting sort rather than any other kind of sort. Why is std::sort not good enough for you? Or - do you actually only care about the counts? If not, what about a Radix sort? etc.

I would separate output logic from the actual sorting algorithm, obtaining something like:

class count_sort
{
std::map<int, size_t> m;

public:

void counting_sort(std::vector<int>& a){
std::for_each(a.cbegin(),
a.cend(),
[this](int i) { m[i]++; });

size_t index = 0;

std::for_each(m.cbegin(),
m.cend(),
[&a, &index](std::pair<int, size_t> const& p) {
for (size_t i = 0; i < p.second; ++i) {
a[index++] = p.first;
};
});
}
};

void display(const std::vector<int>& vec)
{
std::cout << "[";
char* separator = "";

for (int i : vec)
{
std::cout << separator;
separator = ", ";
std::cout << i;
}

std::cout << "]";
}


As a side note, the complexity of both my and your versions is $\Theta(n \log k)$, where $n$ is the length of the input vector, and $k$ is the number of distinct integers. This is $\Theta(n \log n)$, when $k = n$ (all keys in the vector are distinct).

Hope that helps.

• what is the function of [this] and [&a, &index] – coder Aug 14 '17 at 18:55
• [this] allows you using the field std::map<int, int> m. Same logic for [&a, &index]. I have to add that & means "reference", so I don't end up copying data structures. These are called capture lists, yet Google can tell you about them much more than I do. – coderodde Aug 14 '17 at 18:59

Aside from what is said already:

1. Not sure by which coding style you go, but lower case class names are unusual.

2. Separate into several files. A class has a header file and a source file. Somebody who wants to use the class should only require the header. This also holds true for collections of functions. Keep your main source file small.

3. a is no proper variable name. Especially for an input. Neither is m. Use words. (i for the iteration variable is fine though, since it is short lived and everybody knows what it does)

That said, can only repeat from the other answer: This should not be a class. "This is a count sort" does not make sense as a sentence, this is why. Also, every object of it will be extremely short lived. If you want to extend the functionality of something that already exists, use functions.