Comparatori — tu decizi ordinea

De ce contează?

La un concurs de gătit, juriul are o regulă clară de departajare: întâi gustul, la egalitate prezentarea, apoi rapiditatea. Nu reevaluează totul de trei ori — aplică regula o dată, în ordine. Comparatorul este exact această regulă scrisă în cod.

Ce este un comparator

Un comparator e o funcție care îi spune lui sort cum să ordoneze. Primește două elemente, a și b, și întoarce true dacă a trebuie să stea înaintea lui b:

bool cmp(int a, int b) {
    return a > b;   // a inaintea lui b cand e mai mare -> descrescator
}

return a < b; → crescător.
return a > b; → descrescător.

Observația-cheie

Regula de aur: comparatorul descrie relația „strict înainte". Folosește < sau >, niciodată <=/>=. O ordine non-strictă poate produce comportament nedefinit la sortare.

Folosirea cu `sort`

Comparatorul e al treilea argument al lui sort:

#include <iostream>
#include <algorithm>
using namespace std;

bool descrescator(int a, int b) {
    return a > b;
}

int main() {
    int v[6] = {5, 3, 8, 1, 9, 2};
    sort(v, v + 6, descrescator);
    for (int i = 0; i < 6; i++) cout << v[i] << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Comparator pentru structuri

Aici comparatorii devin esențiali: un tip propriu nu are ordine „implicită".

struct Elev {
    string nume;
    int nota;
};

bool dupaNota(const Elev &a, const Elev &b) {
    return a.nota < b.nota;   // crescator dupa nota
}

// sort(v, v + n, dupaNota);

Transmiterea prin const & evită copierea structurilor la fiecare comparație.

Mai multe criterii (departajare)

Tratezi criteriile în ordinea priorității. Rezolvi după primul; doar la egalitate treci la următorul:

bool clasament(const Elev &a, const Elev &b) {
    if (a.nota != b.nota) return a.nota > b.nota;  // 1) nota descrescator
    return a.nume < b.nume;                         // 2) la egalitate, nume crescator
}

Lambda — comparator pe scurt

Pentru comparatori folosiți o singură dată, scrii o funcție anonimă (lambda) direct la apel:

sort(v, v + n, [](const Elev &a, const Elev &b) {
    return a.nota > b.nota;
});

E același comparator, scris mai compact, fără să-i dai un nume separat.

Complexitate

Element	Cost
`sort` cu comparator	O(n log n)
un apel de comparator	O(1) (dacă logica e simplă)

Greșeli frecvente

Capcane la comparatori:

<= în loc de <: încalcă ordinea strictă → comportament nedefinit. Folosește mereu comparație strictă.
Departajare aplicată mereu: dacă tratezi al doilea criteriu chiar și când primul diferă, strici ordinea. Treci la criteriul următor numai la egalitate.
Comparator inconsistent: rezultatul lui cmp(a,b) trebuie să fie opusul lui cmp(b,a) pentru elemente diferite. Logică contradictorie → crash.
Copiere inutilă: comparator pe structuri cu parametri prin valoare copiază la fiecare comparație. Folosește const &.

Recapitulare

Comparatorul întoarce true când primul element trebuie să stea înaintea celui de-al doilea (< crescător, > descrescător).
Pentru structuri e obligatoriu — tipurile proprii n-au ordine implicită; folosește const &.
Mai multe criterii: rezolvi în ordinea priorității și departajezi numai la egalitate pe criteriul anterior.