CODEWITHSUNDEEP
c++sorting
Joshua20072
Joshua20072

Reputation: 3

Sort a string based on the order of another string

I was tasked with ordering a string based on another string assuming everything in the string is also in the sorting string

E.G.

s = "Hello World"

orderString = " odlehwr"

output: " oodlllehwr"

I managed to do it in O(nlogn) time, but I was told after that it should be O(n + m) time and I just don't see how it's possible since it's a sort function, but I hope someone could point me in the right direction.

Here's my original code:

std::string _sortOrder;
std::string _input;

bool customComp(char c1, char c2) {
    //checks to see which is equal first in sequential order
    for (int i = 0; i < _sortOrder.length(); i++) {
        if (_sortOrder[i] == c2) {
            return false;
        }
        else if (_sortOrder[i] == c1) {
            return true;
        }
    }
}

void Question2::SortLetters(char* input, char* sortOrder) {
    //uses strings for maintainability
    _sortOrder = sortOrder;
    _input = input;

    //sorts using the custom comparator based on sortOrder
    std::sort(_input.begin(), _input.end(), customComp);
    std::copy(_input.begin(), _input.end(), input);
}

Upvotes: 0

Views: 675

Answers (1)

scohe001
scohe001

Reputation: 15456

You actually don't need to do any sorting at all here. Since you know that you only have m unique characters, you can make m buckets (in code, this would probably look like a dictionary or a hash table). Then you just need to keep a count for each character.

After that, it's just a matter of looping through the sorted string and repeating each character however many times you saw it.

So the algorithm in pseudocode would look like:

string s = "Hello World";
string ordered = " odlehwr"
dictionary dict;
for (char c in s) {
    dict[c]++;
}

string sorted = "";
for (char c in ordered) {
    sorted += string(c, dict[c]); // repeat c, dict[c] times
}

Upvotes: 2

Related Questions