Grade 12 · Data structures and the STLCitește în română

Sorting with a comparator

Original: Sortare cu comparator

O(n log n)C++1759 lines1 example

The idea

sort(begin, end, cmp) orders by our own rule: cmp(x, y) returns true if x must come before y. Here we sort the contestants of a competition by score in decreasing order, and with equal scores alphabetically by name. The comparator must be 'strict': it returns false for equivalent elements (never <= or >=), otherwise sort may misbehave.

Original description (Romanian)

sort(început, sfârșit, cmp) ordonează după regula noastră: cmp(x, y) întoarce true dacă x trebuie pus înaintea lui y. Aici sortăm participanții unui concurs descrescător după punctaj, iar la punctaj egal alfabetic după nume. Comparatorul trebuie să fie „strict”: pentru elemente echivalente întoarce false (niciodată <= sau >=), altfel sort se poate comporta greșit.

Complexity
O(n log n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

5
Ana 87
Mihai 95
Bogdan 87
Ioana 100
Dan 95

Expected output

Ioana 100
Dan 95
Mihai 95
Ana 87
Bogdan 87

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sort-cu-comparator.cpp
/*
 * Titlu: Sortare cu comparator
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: sort(început, sfârșit, cmp) ordonează după regula noastră: cmp(x, y)
 *            întoarce true dacă x trebuie pus înaintea lui y. Aici sortăm
 *            participanții unui concurs descrescător după punctaj, iar la punctaj
 *            egal alfabetic după nume. Comparatorul trebuie să fie „strict”: pentru
 *            elemente echivalente întoarce false (niciodată <= sau >=), altfel
 *            sort se poate comporta greșit.
 * Complexitate: O(n log n)
 *
 * Exemplu
 * Intrare:
 * 5
 * Ana 87
 * Mihai 95
 * Bogdan 87
 * Ioana 100
 * Dan 95
 * Ieșire:
 * Ioana 100
 * Dan 95
 * Mihai 95
 * Ana 87
 * Bogdan 87
 */
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Participant
{
    string nume;
    int punctaj;
};

bool inainte(const Participant &x, const Participant &y)
{
    if (x.punctaj != y.punctaj)
        return x.punctaj > y.punctaj; // punctajul mai mare primul
    return x.nume < y.nume;           // la egalitate, ordinea alfabetică
}

int main()
{
    int n;
    cin >> n;
    vector<Participant> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i].nume >> p[i].punctaj;
    sort(p.begin(), p.end(), inainte);
    for (const Participant &x : p)
        cout << x.nume << ' ' << x.punctaj << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.