De ce contează?
Un clasament sportiv se ordonează după punctaj — dar la punctaj egal, după golaveraj. Ai nevoie de o regulă clară de comparație între doi concurenți. Sortarea structurilor e exact asta: îi spui calculatorului după ce câmp (și în ce ordine) să le aranjeze.
Problema: sort nu știe ce câmp vrei
std::sort ordonează numere fără probleme, dar o structură are mai multe câmpuri — nu
„ghicește" după care vrei. Îi dai tu regula, sub forma unei funcții de comparare
(comparator).
Comparatorul: cine merge înaintea cui
Comparatorul primește două structuri și returnează true dacă prima trebuie să stea
înaintea celei de-a doua:
#include <iostream>
#include <algorithm>
using namespace std;
struct Elev {
char nume[30];
double nota;
};
bool dupaNota(const Elev& a, const Elev& b) {
return a.nota > b.nota; // nota mai mare -> mai in fata (descrescator)
}
int main() {
int n;
cin >> n;
Elev v[1000];
for (int i = 0; i < n; i++) cin >> v[i].nume >> v[i].nota;
sort(v, v + n, dupaNota); // sortam dupa nota, descrescator
for (int i = 0; i < n; i++) cout << v[i].nume << " " << v[i].nota << "\n";
return 0;
}return a.nota > b.nota dă ordine descrescătoare (nota mare în față). Cu < ai
crescător. Comparatorul e singurul loc unde decizi criteriul — schimbând câmpul sau semnul,
schimbi sortarea.
Departajare: criterii multiple
La note egale, vrei o ordine clară (ex. alfabetică după nume). Adaugi un al doilea criteriu:
bool cmp(const Elev& a, const Elev& b) {
if (a.nota != b.nota) return a.nota > b.nota; // intai dupa nota (desc)
return strcmp(a.nume, b.nume) < 0; // la egalitate, alfabetic
}Întâi compari câmpul principal; doar dacă e egal, treci la al doilea.
Ordinea criteriilor în comparator dă prioritatea. „Întâi nota, apoi numele" se citește exact ca în cod: verifici nota, și doar la egalitate te uiți la nume. La fel adaugi al treilea, al patrulea criteriu.
Complexitate
| Operație | Timp | Spațiu |
|---|---|---|
std::sort | O(n log n) | O(log n) |
std::sort e rapid (O(n log n)); comparatorul tău rulează la fiecare comparație, deci
ține-l simplu.
Capcane reale la sortarea structurilor:
- Comparator inconsistent: folosești
<=în loc de<→ încalci „strict weak ordering" șisortpoate da crash sau rezultat greșit. Compară strict. - Uiți departajarea: la valori egale pe criteriul principal, ordinea e nedefinită; adaugă un al doilea criteriu dacă enunțul o cere.
- Compari câmpul greșit: returnezi după alt câmp decât cel cerut. Verifică ce câmp decide ordinea.
- Sortezi vectori paraleli separat: rupi legătura dintre câmpuri. Sortează structura întreagă cu un comparator.
De reținut
- Sortezi structuri cu
std::sort(v, v+n, cmp)și un comparator care decide ordinea după un câmp. cmpreturneazăa.camp < b.camp(crescător) sau>(descrescător); strict, nu<=.- Departajezi la egalitate adăugând criterii suplimentare, în ordinea priorității.