Sort int array by frequency then value

Question

Problem

Take an array of ints as input and run a special sorting algorithm on it. This algorithm must first sort by int frequency, less frequent first, then sort by value.

For example [4,5,6,5,4,3] is sorted to [3,6,4,4,5,5].

I'm looking for feedback on my use of data structures to implement this sort, memory management, any redundancies, and other general optimizations I can make. No need to give feedback on how I capture input in main since that is not my priority here.

Code

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int * customSort(int * arr, int n) {
  unordered_map<int, int> frequencyMap;
  for (int i = 0; i < n; i++) {
    auto mapIt = frequencyMap.find(arr[i]);
    if (mapIt == frequencyMap.end()) {
      frequencyMap.insert(make_pair(arr[i], 1));
    } else {
      frequencyMap[arr[i]]++;
    }
  }

  map<int, set<int>> orderedfrequencyMap;
  for (auto &p : frequencyMap) {
    auto mapIt = orderedfrequencyMap.find(p.second);
    if (mapIt == orderedfrequencyMap.end()) {
      set<int> s = {p.first};
      orderedfrequencyMap.insert(make_pair(p.second, s));
    } else {
      (*mapIt).second.insert(p.first);
    }
  }

  int arrI = 0;
  int solution[n];
  for (auto &p : orderedfrequencyMap) {
    for (auto element : p.second) {
      for (int i = 0; i < p.first; i++) {
        arr[arrI] = element;
        cout << element << endl;
        arrI++;
      }
    }
  }

  return solution;
}

int main() {
    int n;
    cin >> n;

    int arr[n];

    int element;
    for (int i = 0; i < n; i++) {
      cin >> element;
      arr[i] = element;
    }

    customSort(arr, n);

    return 0;
}

Answer 1

Headers

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

Some issues here. You definitely don't need all those headers. Proon out the ones you don't need. The problem with putting them all in is that this can hide missing dependencies (if this was a header file and included by other header files).

Normally I don't care much about the order of headers (usually there is some logic there and everybody has their own). But sorting by filename length of include seems a bit odd. I have seen people sort by alphabetical order (not my favorite but it has options and I see the merit). Personally I put things into logical (to me) groups; I put container stuff together, stream stuff together, algorithm stuff together and meta programming stuff together. I put all my C++ headers before my C header.

Maps

If you access an element in a map and it does not exist then it is automatically created and "zero-initialized". This means you don't need to search and conditialy update.

  unordered_map<int, int> frequencyMap;
  for (int i = 0; i < n; i++) {
    auto mapIt = frequencyMap.find(arr[i]);
    if (mapIt == frequencyMap.end()) {
      frequencyMap.insert(make_pair(arr[i], 1));
    } else {
      frequencyMap[arr[i]]++;
    }
  }

Can be simplified too:

  unordered_map<int, int> frequencyMap;
  for (int i = 0; i < n; i++) {
      ++frequencyMap[arr[i]];
  }

VLA

Variable length arrays are an extension of C (part of C99). They were never part of the C++ standard. So this is not legal C++.

cin >> n;
int arr[n];

Your compiler supports it as an extension to the language but its not a good idea to use it. We use std::vector as a better alternative:

cin >> n;
std::vector<int> arr(n);

This also allows you to use range based for loops:

  unordered_map<int, int> frequencyMap;
  for (int val: arr) {
      ++frequencyMap[val];
  }

Order by frequency.

I like your idea of ordering by frequency using a std::map but it becomes clunky when you also have to order by value (and thus have a map of std::set). I would simply copy the frequency info into a vector and use a sort.

using Val = std::pair<int, int>;
std::vector<Val>  values(std::begin(frequencyMap), std::end(frequencyMap));
std::sort(std::begin(values), std::end(values), [](Val const& lhs, Val const& rhs)
  {
    return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
  });

Standard Issues from Beginners

Don't use

using namespace std;

This is a crutch that will break for you. Don't get into the habit of using it when it breaks it is not obvious and can lead to hours of debugging. The reason the standard namespace is called std and not standard is so prefixing object in the standard namespace is not that burdensome.

std::vector<int>  val;  // not that hard to add std::

Don't return an array from a function

 return solution;

You are returning the address of a local variable. Once this goes out of scope that variable no longer exists. So you have an invalid pointer returned. This is also another good reason to use std::vector as the copy/move semantics will correctly move it from the current scope to the calling scope.

PS. Your compiler should warn you about this.

No need to use return in main

return 0;

The compiler plants a return 0 at the end of main.

By not planting a return in main() it is an indication that your application does not have a failing state (usual for simple code). If it does have a user inserted return 0 I always start looking for other places it could return an error code. By not putting a return 0 you indicate to me that there is no error situation and I don't have to look for it.

Prefer pre increment to post increment

for (int i = 0; i < p.first; i++)

for (int i = 0; i < p.first; ++i)

In this case there is basically no difference. But there are situations where the post increment is slightly more complex.

What happen if we change i from an int into an iterator. Then it is a class the executes a function. Most iteratros behave like POD types with pre/post increment but to do that the post increment is slightly more complex. So why not use the one that will always give you optimal code (even if you change the type). So prefer pre-increment.

Prefer '\n' over std::endl

The difference is that std::endl will force a flush. In simple things like this it makes no difference. But if you are outputting a large amount of information then the extra flush can cause significant performance degradation.

The streams will auto flush themselves and having a human forcing a flush is always non optimal. So prefer to get the same resutls but at optimal speed with '\n'.

Pointer short hand

You should note that we have a shortcut pointer notation.

(*mapIt).second

// Shorthand as:
mapIt->second

Avoid short variable names

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

This is great if your for loop is two lines long. But if the loop grows and becomes more complex then searching for all instances of i becomes a pain because of all the false positives.

Believe me just because your loop only covers two lines today, in ten years after thousands of bug fixes it will not look as neat. So give me something that is easy to search for in the code base.

I know a lot of people like using i as a loop variable. But this is a hold over from Foortran. Please use longer identifiers it will not cost you that much and the maintainer will not hunt you down with an axe.

Looks Like this:

#include <unordered_map>
#include <vector>
#include <iostream>
#include <iterator>

std::vector<int> customSort(std::vector<int> const& arr)
{
    std::unordered_map<int, int> frequencyMap;
    for (int val: arr) {
        ++frequencyMap[val];
    }

    using Val = std::pair<int, int>;
    std::vector<Val>  values(std::begin(frequencyMap), std::end(frequencyMap));
    std::sort(std::begin(values), std::end(values), [](Val const& lhs, Val const& rhs) {
            return (lhs.second < rhs.second) || (lhs.second == rhs.second && lhs.first < rhs.first);
          });

    std::vector<int> result;
    result.reserve(arr.size());
    for(auto const& val: values) {
        for(int loop = 0;loop < val.second; ++loop) {
            result.push_back(val.first);
        }
    }
    return result;
}

int main()
{
    std::vector<int> arr;

    int n;
    std::cin >> n;
    std::copy_n(std::istream_iterator<int>(std::cin), n,
            std::back_inserter(arr));

    std::vector<int> sorted = customSort(arr);
    std::copy(std::begin(sorted), std::end(sorted),
              std::ostream_iterator<int>(std::cout, "\n"));
}