Created
December 7, 2014 03:48
-
-
Save LemonPi/ee960d8e2bd425ba8838 to your computer and use it in GitHub Desktop.
Sorting based on frequency of elements into descending order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <map> | |
#include <algorithm> // fill_n, trivially replaceable | |
// sorts in place based on frequency | |
template <typename Iter> | |
void freq_sort(Iter begin, Iter end) { | |
using T = typename Iter::value_type; | |
if (begin == end) return; | |
T current {*begin}; | |
std::map<size_t, std::vector<T>> frequency; | |
// map allows in-order traversal (implemented as binary search tree) | |
size_t count {1}; | |
auto cur = begin + 1; | |
for (; cur != end; ++cur) { | |
// assuming condition 1 is true (can't have multiple groups of same val) | |
if (*cur == current) ++count; | |
else { | |
frequency[count].push_back(current); // last value | |
count = 1; | |
current = *cur; | |
} | |
} | |
// put last count back in | |
frequency[count].push_back(current); | |
// second pass to put values in place | |
cur = begin; | |
for (auto entry = frequency.rbegin(); entry != frequency.rend(); ++entry) { | |
// fill frequency amount of times by the actual value starting at cur | |
for (auto val : entry->second) // vector of values with same frequency | |
cur = std::fill_n(cur, entry->first, val); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment