Is there an easier way of sorting this?

Hello, I am trying to figure out an easier way of sorting based on frequency to be specific:
"Sort the alphabet in decreasing order based on the frequency. If two or more symbols have the same frequency, then use the symbols ASCII values (higher ascii value = higher priority).

For context here's an example input:
aaaeeeiiiooouuuuuuuuuuuuuuuuaaeeeeeeeiiiiiiiiiiiiiiiiiiiiiiiiiiiiaaaaa

This would be:
i : 31
u : 16
e : 10
a : 10
o : 3

in descending order. Since 'e' has a higher ascii value of 101 compared to 'a' which has an ascii value of 97 'e' would come before 'a' (They have the same frequency)

The problem is I want to find an easier more simple way to sort this in descending order maybe using the std::sort or/and std::greater, but I'm not sure how I'd do it. Here's some info on what I'm using:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct variables{

    char symbol;
    int freq;
    string code;
    string* pointerContent;

};

int main(){

struct variables structVariables [128];
//...some functions calls and stuff here

//how to use sort function here?
}


I already have a way of sorting in descending order but it seems a bit repetitive with what I'm doing and it's a bit long, any thoughts? Here's the code I had previously.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::map<char, int> priorityMap; 
    std::map<char, int>::iterator priorityItr;

    for(long j = 0; j < (*contents).length(); j++){ 
        priorityMap[(*contents)[j]]++;
    }

    int mapSize = map.size();

    while(mapSize--){ 

        unsigned int currMax = 0;
        char maxChar;

        for(priorityItr = priorityMap.begin(); priorityItr != priorityMap.end(); ++priorityItr){
            if(priorityItr->second > currMax || (priorityItr->second == currMax && priorityItr->first > maxChar)){ 
                maxChar = priorityItr->first;
                currMax = priorityItr->second;
            }
        }

        cout << "maxChar: " << maxChar << ", currMax: " << currMax << endl;
        priorityMap.erase(maxChar); 
    }

Last edited on
It's fairly inefficient, algorithmically. You're taking O(n^2 (log n)^2) (over the number of distinct characters) to do something that could be easily done in O(n log n).

Consider this class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Date{
    int y, m, d;
    bool operator<(const Date &other) const{
        if (this->y < other.y)
            return true;
        if (this->y > other.y)
            return false;
        
        if (this->m < other.m)
            return true;
        if (this->m > other.m)
            return false;
            
        return this->d < other.d;
    }
};

std::vector<Date> dates;
//populate
std::sort(dates.begin(), dates.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <cctype>

int main()
{
    if( std::ifstream file{__FILE__} )
    {
        // read in the frequencies
        std::map<char,int> freq_map ;
        char c ;
        while( file.get(c) ) ++freq_map[c] ;

        // sort on descending frequencies
        std::vector< std::pair<int,char> > vec;
        for( auto[ch,f] : freq_map ) vec.push_back( { f, ch } ) ;
        std::sort( vec.begin(), vec.end(), std::greater{} ) ;

        // print results
        for( auto[f,ch] : vec )
        {
            if( std::isprint( static_cast<unsigned char>(ch) ) ) std::cout << ch ;
            else std::cout << "char(" << int(ch) << ") " ;
            std::cout << "  frequency " << f << '\n' ;
        }
    }
}

http://coliru.stacked-crooked.com/a/339874a649e4680b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <map>
#include <set>
using namespace std;

using PR = pair<char,int>;

struct comp
{
   bool operator()( PR a, PR b ){ return a.second != b.second ? a.second > b.second : a.first > b.first; }
};

//-----------------------------------------------

void chart( const string &input )
{
   map<char,int> freq;
   for ( char c : input ) freq[c]++;
   set<PR,comp> S( freq.begin(), freq.end() );
   for ( PR p : S ) cout << p.first << " : " << p.second << '\n';
}

//-----------------------------------------------

int main()
{
   chart( "aaaeeeiiiooouuuuuuuuuuuuuuuuaaeeeeeeeiiiiiiiiiiiiiiiiiiiiiiiiiiiiaaaaa" );
}


i : 31
u : 16
e : 10
a : 10
o : 3
Topic archived. No new replies allowed.