Sort the array by frequency

Question:

Sort the array by frequency:

Input: [0, 1, 1, 2,2,2, 3, 4, 5,5,5,5,6,6,6,6,6,7,8,8,9,9,9]

Output:[0,3,4,7,1,1,2,2,2,8,8,2,2,2,9,9,9,5,5,5,5,6,6,6,6,6].

Answer:

#include<iostream>

#include<unordered_map>

#include<vector>

#include<utility>

#include<algorithm>

using namespace std;

struct wrapper{

        int value;

int freq;

wrapper():value(0),freq(0){};

};

bool cmp(wrapper &lhs, wrapper &rhs){

if(lhs.freq < rhs.freq) return true;

                else if(lhs.freq > rhs.freq) return false;

else return (lhs.value < rhs.value);

}

void sortbyfreq(int a[],int len){

wrapper *w = new wrapper[len];               //Important!

/* Method 1. No hashmap for count freq. 

sort(a,a+len);

int count = 0, k= 0;

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

if(i<len && i-1>=0 && a[i]==a[i-1] || i==0){

count++;

}

else{      //also include i=len,last initialize execute!!!

for(int j=0;j<count;j++){

                 w[k].value= a[i-1];

w[k].freq = count;      //Important!

k++;

}

count = 1;

}

}

*/

       //Method 2, use hashmap for count freq!

unordered_map<int,int> mmap;

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

   if(mmap.find(a[i])==mmap.end()){

   mmap[a[i]]=1;

}

else{

mmap[a[i]]++;

}

}

int k=0;

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

w[k].value= a[i];

   w[k].freq = mmap[a[i]];     

   k++;

}

sort(w,w+len,cmp);

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

a[i] = w[i].value;

}

}

int main() {

    int arr [] = {0,1,2,3,2,1,1,1};

    int len = sizeof(arr)/sizeof(int);

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

cout << arr[i] << ' ';

    }

    cout << endl;

    sortbyfreq(arr, len);

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

cout << arr[i] << ' ';

    }

    cout << endl;

getchar();

    return 0;

}