CODEWITHSUNDEEP
algorithmsorting
Evgeny Lazin
Evgeny Lazin

Reputation: 9413

Sort an array which is sorted in a different way

I have an array of tuples of type (int, char). It is sorted in lexicographical order:

[(0, 'a'), (0, 'b'), (0, 'c'), (1, 'a'), (1, 'b'), (1, 'c') ...]

I need to sort it by second element first and then by first element:

[(0, 'a'), (1, 'a'), ..., (0, 'b'), (1, 'b'), ..., (0, 'c'), (1, 'c'), ...]

What sorting algorithm fit this case the best?

Upvotes: 0

Views: 97

Answers (3)

dingalapadum
dingalapadum

Reputation: 2177

Asymptotically it doesn't make a difference whether you have it sorted in a different manner or not at all. Hence, if you don't care about constant factors, you can use any sorting algorithm you like. The important thing for this task is not so much which algorithm you use, but rather how to apply it. So for the sake of the example (in C++, other langs will provide something similar I guess) we will just use sort() as provided in <algorithm>

To make it very explicit:

//the tuple
struct intChar{
    int i;
    char c;
};

//define how our struct evaluates under '<'
bool operator<(const intChar &lhs, const intChar &rhs){
    if(lhs.c == rhs.c){
        return lhs.i < rhs.i;
    }
    return lhs.c < rhs.c;
}

Here we say we only want to sort according to the int, if the characters are the same. Else sort by char.

Then you can just use the regular sorting algorithm: http://www.cplusplus.com/reference/algorithm/sort/ i.e:

#include <algorithm>

vector<intChar> toSort;

/*... fill vector ...*/
sort(toSort.begin(), toSort.end());

Note: you could actually define other comparisons and pass the comparison-method to be used to the sort method. Here we just overloaded <.

Now, if you care about performance and want to squeeze the last bit out then, as suggested in the other solution, you should just use a stable-sort on your second entry. However, the benefit of the above solution is that it will also work for a completely unordered array. If you don't need the general solution and want to drop that overhead and profit from the information you got about your input you can just remove the part:

if(lhs.c == rhs.c){
    return lhs.i < rhs.i;
}

And then use stable_sort() instead of sort(). This will save you a constant factor, which as I said in the very beginning does not make any difference for the asymptotic runtime which is O(n*log(n)) in any case.

Upvotes: 2

Bert te Velde
Bert te Velde

Reputation: 853

A simple method would be:

  1. create a collection where you put the tuple-elements colled together, but "reversed": {1,'a'} => "a1" (depending on the case you may need to allow for suitable spaces and/or zeros inserted, for example {1,'a'} => "a01" if the chars are always single but the numbers may have two digits).

  2. Sort

  3. Unpack again.

The pack/unpack steps are O(n), the sorting is the step that determines performance: O(nLogn)

Upvotes: 0

Fabian Barney
Fabian Barney

Reputation: 14549

Short answer: Just stable-sort it by your second element and you're done.

Longer answer:
Use a stable sorting algorithm and first sort by your first element and then by your second element.

A stable sorting guarantees that equal elements remain in the same order.

However if your input is already sorted by your first element then you do not have to sort it again. Just stable-sort it by your second element and you're done.

Most famous stable sorting alg is most probably MergeSort.

Upvotes: 3

Related Questions