Group and sort a vector by common / repeating elements in C ++

Question

Suppose I have a vector as follows:

std::vector<int> v = {3, 9, 7, 7, 2};

I would like to sort this element vector so that the vector is saved as 77932. So, first we save the common elements (7), then we sort the remaining elements from the highest to the lowest.

If I have a vector as follows

std::vector<int> v = {3, 7, 7, 7, 2};

Here it will lead to 77732.

Same for

std::vector<int> v = {7, 9, 2, 7, 9};

this should result in 99772 because 9s are above 7s.

Last example

std::vector<int> v = {7, 9, 7, 7, 9};

this should lead to 77799, because there are more 7s than 9s.

What could be the fastest algorithm to implement this?

Answer 1

std::multiset . , std::tie:

std::vector<int> data = {7, 9, 2, 7, 9};
std::multiset<int> count(data.begin(), data.end());
std::sort(
    data.begin()
,   data.end()
,   [&](int a, int b) {
        int ca = count.count(a);
        int cb = count.count(b);
        return std::tie(ca, a) > std::tie(cb, b);
    }
);
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));

1

: count(n) std::multiset , . , std::unordered_map :

std::vector<int> data = {7, 9, 2, 7, 9};
std::unordered_map<int,int> count;
for (auto v : data)
    count[v]++;
std::sort(
    data.begin()
,   data.end()
,   [&](int a, int b) {
        return std::tie(count[a], a) > std::tie(count[b], b);
    }
);
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));

2.

Answer 2

, , , std::sort -

std::unordered_map<int, size_t> frequency;
std::for_each(v.begin(), v.end()
            , [&](int i) { ++frequency[i]; });
std::sort(v.begin(), v.end()
        , [&](int lhs, int rhs)
          { 
            return std::tie(frequency[lhs], lhs) < std::tie(frequency[rhs], rhs);
          }); 

Answer 3

, - , , (, , , 2 ):

void custom_sort(vector<int> &v)
{
if (v.size() < 2)
    return;

sort(v.begin(), v.end(), std::greater<int>());

vector<int> dupl;
vector<int> singl;
int d;
bool dv = false;
for (int i = 1; i < v.size(); ++i)
{
    if (!dv)
    {
        if (v[i - 1] == v[i])
        {
            d = v[i];
            dv = true;
            dupl.push_back(d);
        }
        else
        {
            singl.push_back(v[i - 1]);
        }
    }
    else
    {
        dupl.push_back(d);
        if (v[i] != d)
            dv = false;
    }
}

if (!dv)
    singl.push_back(v.back());
else
    dupl.push_back(d);

auto mid = copy(dupl.begin(), dupl.end(), v.begin());
copy(singl.begin(), singl.end(), mid);
}

, - inverview, , ...: -)

Answer 4

EDIT, .

, .. , counting sort ( , ).

void custom_sort(std::vector<int>&v, const int N)
// assume that all elements are in [0,N[ and N elements fit into cash
{
  vector<int> count(N);
  for(auto x:v)
    count.at(x) ++;   // replace by count[x]++ if you're sure that 0 <= x < N
  int i=0;
  // first pass: insert multiple elements
  for(auto n=N-1; n>=0; --n)
    if(count[n] > 1)
      for(auto k=0; k!=count[n]; ++k)
        v[i++] = n;
  // second pass: insert single elements
  for(auto n=N-1; n>=0; --n)
    if(count[n] == 1)
      v[i++] = n;
}

Answer 5

O (N Log (N)) O (N).

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>

int main(){

    typedef std::pair<int, int> pii;
    typedef std::vector< int > vi ;
    typedef std::vector< pii > vii;

    vi v = {7, 9, 7, 7, 9};

    //O( N log(N) )
    std::sort(v.begin(), v.end());


    vii vc;
    vc.reserve(v.size());

    // O (N)  make (cnt, value) pair of vector
    for(size_t i = 0; i != v.size(); ++i)
    {
        if (vc.empty() ||  v[i] != vc.back().second ){
           vc.push_back( pii(0, v[i]) ) ;
        }

        vc.back().first ++ ;
    }

    // O (N Log(N) )  sort by (cnt, value)
    std::sort( vc.begin(), vc.end() ) ;

    // O(N)   restore they, reverse order.
    v.clear();
    for(int i = 0; i < (int)vc.size(); ++i){
        int rev_i = vc.size() - i - 1;
        int cnt =  vc[rev_i].first;
        for(int k = 0; k < cnt; ++k)
          v.push_back( vc[rev_i].second ) ;
    }

    /////////////////////////

    for(size_t i = 0; i != v.size(); ++i){
        printf("%4d, ", v[i]);
    }
    printf("\n");
}