Step 5 of 6
Stability and custom comparators
A sort is stable if equal elements keep their original relative order. It sounds like a detail, but it matters whenever the input order means something (arrival time, sign-up order) or when you sort by one key after another.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Order {
std::string id;
int priority;
};
int main() {
// Arrival order: a1 came first, then b2, and so on.
std::vector<Order> q = {{"a1", 2}, {"b2", 1}, {"c3", 2}, {"d4", 1}, {"e5", 2}};
std::stable_sort(q.begin(), q.end(), [](const Order& x, const Order& y) {
return x.priority < y.priority; // strictly less: a valid comparator
});
for (const auto& o : q) std::cout << o.id << "(" << o.priority << ") ";
std::cout << "\n";
}
b2(1) d4(1) a1(2) c3(2) e5(2)
Within each priority, orders are still in arrival order: b2 before d4, and a1, c3, e5 in sequence. std::sort might have mixed them up.
std::sort vs std::stable_sort
std::sort: not stable, usually slightly faster.std::stable_sort: stable. Use it whenever ties must keep their order.
Comparators must be strict
A comparator answers "must a come strictly before b?". For equal elements it must return false both ways. So use < or >, never <= or >=. Breaking this rule is undefined behavior: results can be wrong, and with std::sort it can even read outside the array and crash.
For "highest score first", compare with >: return a.score > b.score;.
Your task
Write void rank(std::vector<Entry>& v) that orders entries by score, highest first. Entries with equal scores must stay in their original (sign-up) order.
Challenge 2
Write void order(std::vector<Player>& v) sorting by team (alphabetical), then score (highest first), then name (alphabetical). Compare with std::tie, which builds tuples that compare field by field; flip a and b for the score so it sorts descending.
Challenge 3
Write std::vector<int> sort_indices(const std::vector<int>& v), the indexes of v in the order that would sort it (an "argsort"), with equal values keeping their index order. Fill a vector with 0..n-1, then std::stable_sort it with a comparator that compares v[a] < v[b].