CODEWITHSUNDEEP
c++algorithmsortingvector
Rosen Karadinev
Rosen Karadinev

Reputation: 205

Vector Sort Algorithm, sort only elements bigger then 0

I have to sort a vector of structs. Let's say the struct has two members:

Struct game
{
  string name;
  int rating;
};

So I have created a std::vector<game> games and simple sort them by rating.

std::sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});

Everything is alright so far. The problem is if all games have rating value 0, they mix. Simply put I have to sort only elements with rating bigger than zero. Let's give you an example:

All games are pushed in the vector by names in alphabetic order and rating 0, when a sort is triggered, the alphabet order gets violated.

Example before sort:

"A_Game", "B_Game", "C_Game", "E_Game", "G_Game", etc. (continue with all next letters)

after sort (all games are with rating 0):

"G_Game", "S_Game", "P_Game", "M_Game", "L_Game", "I_Game", etc.

I need to sort only these games that have rating bigger than 0. Thanks in advance.

Upvotes: 4

Views: 189

Answers (5)

JVApen
JVApen

Reputation: 11317

std::sort indeed doesn't guarantee any ordering for when elements compare equal. std::stable_sort guarantees that the original ordering gets kept if it compares equal. (See the other answers)

When in doubt about the original order, I like to explicitly sort with all of the criteria:

std::sort(games.begin(),games.end(), [](game const & info1, game const & info2)
{
    if (info1.rating != info2.rating)
        return info1.rating > info2.rating;

    return info1.name < info2.name;
});

In the above, I prefer to use the following pattern

if member1 different
    return compare member1
if member2 different
    return compare member2

return compare member<last> OR compare pointers

This pattern is easily recognizable and easy extendable when you add extra members.

Ideally, when you want to use this sorting at other places, you make this a function with an unambiguous name. (Don't use operator< as this causes confusion, since the game titles could as well be used as a logical way of sorting)

Upvotes: 1

Ely
Ely

Reputation: 11174

You can use stable_sort instead of sort. This would be the best option for the question.

You can also modify the sort so that when two games have equal rating, sort alphabetically comparing the two names (or any other condition that might come up in the future). It might look like this.

std::sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    if (info1.rating == info2.rating)
        return info1.name.compare(info2.name);

    return info1.rating > info2.rating;
});

Upvotes: 1

uv_
uv_

Reputation: 773

You can use std::stable_sort().

However, you can keep using std::sort() and make the comparator return true for games with the same rating (so the relative order is kept), by changing the condition to

return !(info1.rating < info2.rating)

Upvotes: 2

jfMR
jfMR

Reputation: 24788

std::sort() is not a stable sorting algorithm, i.e., elements with equivalent keys may not preserve the original order between them after being sorted.

You can use std::stable_sort() instead of std::sort():

std::stable_sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});

As its name already suggest, std::stable_sort() implements a stable sorting algorithm.

Upvotes: 5

Vittorio Romeo
Vittorio Romeo

Reputation: 93334

You can use std::stable_sort to prevent moving around elements that are not affected by the sorting criteria.

std::stable_sort(games.begin(),games.end(), [](game& info1, game& info2)
{
    return info1.rating > info2.rating;
});

Upvotes: 11

Related Questions