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;
}
  • 8
    Please don't remove your header includes - not only does it slow down those of us who want to compile your code ourselves, but we frequently find improvements to make in that respect (missing includes, unnecessary includes, C includes, for example). Same goes for namespace std: we want to see your actual code, not some mangled version of it. Thanks! – Toby Speight Dec 6 at 17:42
  • 5
    Don't remove your includes. As part of the code review I want to copy and paste it into a file and compile it. Having to add the includes back adds to my work load. Also if you leave the includes I can spot where you have bad includes. – Martin York Dec 6 at 17:47
  • 1
    Use your real code. – Nic Hartley Dec 6 at 20:20
  • Thanks for the feedback everyone, I will remember this in the future. Added my includes and removed the namesapce comment, as my real code did originally use the bad practice global using statement so myself some time in implementing this prototype. – greg Dec 6 at 20:55
up vote 15 down vote accepted

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"));
}
  • Excellent response, thanks for breaking it down in the way you have. Very easy to understand how I can refactor now. In the Order by frequency section what is sing in sing Val = std::pair<int, int>;?. Also in the Prefer pre increment to post increment you mention most iterators behave like POD types, what are POD types? – greg Dec 6 at 18:32
  • 1
    Missed cut and paste: using Val = std::pair<int, int>; This is the modern C++ way of doing typedef. – Martin York Dec 6 at 19:13
  • 1
    POD: Plain old data. Integers/char etc. When you increment an integer. It is post increment it increments the value but returns the original value to be used in the expression. – Martin York Dec 6 at 19:14
  • IMHO there is one huge problem with the suggested solution: the customSort function does not in fact sort it just prints so maybe name printInCustomOrder would be more appropriate name. Consequently there is rather big part missing (how would you go about returning? reorder the input? return a smart pointer?). – wondra Dec 7 at 7:33
  • @wondra: No simply return the vector. Because of return value optimization returning a vector is not expensive. In older C++ versions this was achieved via compiler optimizations in modern C++ it is explicitly part of the language and requires a move. – Martin York 2 days ago

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.