Sortare și ordonare în C++: algoritmul de bază, chei de sortare și criterii multiple

Sortarea apare la atestat în 10 probleme din cele publicate aici, dar aproape niciodată în forma „ordonează crescător acest vector". Enunțul cere, aproape de fiecare dată, ordonarea după altceva decât valoarea însăși: după suma cifrelor, după modulul unui număr complex, după media unui elev, după valoarea zecimală a unei fracții.

De aceea partea grea nu e algoritmul — el se scrie o dată și se refolosește — ci identificarea criteriului și mutarea corectă a datelor care merg împreună.

Algoritmul de bază: sortarea prin interschimbare

E cel mai scurt algoritm de sortare care se poate scrie corect din prima și e perfect suficient pentru limitele de la atestat:

for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
        if (v[j] < v[i]) {
            int t = v[i]; v[i] = v[j]; v[j] = t;
        }

Se citește: pentru fiecare poziție i, caută printre cele de după ea vreun element mai mic și adu-l în față. După ce bucla exterioară termină pasul i, poziția i conține valoarea ei definitivă.

Pentru ordine descrescătoare se schimbă un singur caracter: v[j] > v[i].

Algoritmul face aproximativ n²/2 comparații. La n = 10000 înseamnă 50 de milioane de pași — rulează în sub o secundă. Peste această limită ai nevoie de sort() din <algorithm>, dar subiectele de atestat nu ajung acolo.

Probleme: modulele numerelor complexe, descrescător · ordonarea fracțiilor

Tehnica 1 — Sortare după o valoare calculată

Când criteriul nu e valoarea însăși, ai două variante. Prima e să recalculezi criteriul la fiecare comparație. A doua, mult mai bună, e să-l calculezi o singură dată, la citire, și să-l ții într-un vector paralel:

for (int i = 0; i < n; i++) {
    cin >> v[i];
    cheie[i] = sumaCifrelor(v[i]);     // criteriul, calculat o data
}

Apoi sortarea compară cheile, dar interschimbă ambii vectori:

if (cheie[j] < cheie[i]) {
    int t = v[i];     v[i] = v[j];         v[j] = t;
    t = cheie[i];     cheie[i] = cheie[j]; cheie[j] = t;   // obligatoriu
}

A doua linie e cea care se uită. Fără ea, cheile rămân în ordinea inițială iar sortarea compară numere cu criteriile altor numere. Rezultatul iese aproape ordonat — exact genul de greșeală care trece la o verificare rapidă.

Vectorii paraleli sunt o soluție bună când ai două informații legate. Când ai trei sau mai multe, treci la struct (vezi tehnica 3).

Probleme: sortare după suma cifrelor · modulele numerelor complexe · ordonarea fracțiilor

Tehnica 2 — Criteriu secundar la egalitate

Unele enunțuri precizează ce se întâmplă când două elemente au aceeași cheie: „dacă două numere au aceeași cifră de control, ele se vor sorta crescător după valoare". Condiția devine dublă:

if (cheie[j] < cheie[i] || (cheie[j] == cheie[i] && v[j] < v[i])) { ... }

Se citește: interschimbă dacă al doilea are cheia mai mică, sau dacă au chei egale și valoarea mai mică.

Parantezele sunt obligatorii. Fără ele, && se leagă altfel decât intenționezi și condiția devine greșită exact în cazurile de egalitate — adică fix acolo unde o testează subiectul.

Când enunțul spune în schimb „nu contează ordinea lor", ești liber: orice algoritm merge, și nu trebuie să adaugi nimic.

Probleme: sortare după cifra de control

Tehnica 3 — Date structurate

Când fiecare element are mai multe câmpuri care trebuie să rămână împreună (nume + medie, numărător

• numitor), vectorii paraleli devin fragili: e prea ușor să interschimbi unul și să uiți celălalt.

Soluția e struct. Toate câmpurile se mută într-o singură operație:

struct Elev {
    char nume[30];
    float medie;
};

Elev e[35], t;
...
if (e[j].medie > e[i].medie) { t = e[i]; e[i] = e[j]; e[j] = t; }

Observă că interschimbarea e identică cu cea de la numere — atribuirea între variabile de tip struct copiază toate câmpurile deodată. Asta e și motivul pentru care struct e mai sigur decât doi vectori ținuți în paralel.

Probleme: elevii ordonați după medie

Tehnica 4 — Valori distincte

„Afișează valorile distincte, în ordine crescătoare" e o cerință frecventă. Ordinea operațiilor contează:

1. sortează toate valorile;
2. parcurge o dată și afișează un element doar dacă diferă de cel dinaintea lui.

for (int i = 0; i < n; i++)
    if (i == 0 || v[i] != v[i - 1])
        cout << v[i] << " ";

După sortare, valorile egale ajung alăturate, deci o singură comparație cu vecinul din stânga e de ajuns. i == 0 tratează primul element, care n-are vecin în stânga — fără el, citești v[-1].

Dacă valorile sunt mici și mărginite (de exemplu 0..1000), alternativa e un vector de frecvențe: numeri aparițiile și parcurgi la final crescător. E mai rapid și nu cere sortare deloc.

Probleme: numerele distincte din două fișiere · valori distincte și maxim

Tehnica 5 — Când datele sunt deja sortate

Câteva subiecte îți spun din enunț că datele vin ordonate. Asta nu e o informație decorativă: e o scurtătură.

Dacă o mulțime B e sortată și vrei să știi dacă încape întreagă între două valori, nu verifici toate elementele — verifici doar capetele:

if (a[i] < b[0] && b[n - 1] < a[i + 1]) { ... }

Tot ce e între b[0] și b[n-1] e automat în interval. Verificarea tuturor elementelor e corectă, dar semnalează că n-ai folosit ipoteza din enunț.

Probleme: intercalarea a două mulțimi sortate

Tehnica 6 — Secvențe ordonate: caută, nu sorta

Atenție la enunțurile care conțin cuvântul „ordonat" dar nu cer sortare. „Cea mai lungă secvență de caractere consecutive în care literele sunt ordonate alfabetic" înseamnă că trebuie să găsești o porțiune deja ordonată, nu să rearanjezi nimic.

Tiparul e de secvență maximală: extinzi cât timp proprietatea se păstrează, reții cea mai bună, apoi sari după capătul găsit.

int i = 0;
while (i < n) {
    int j = i;
    while (j + 1 < n && s[j + 1] >= s[j]) j++;
    if (j - i + 1 > lung) { lung = j - i + 1; start = i; }
    i = j + 1;                      // SARI peste secventa analizata
}

i = j + 1 e detaliul important. Cu i++ reiei din interiorul unei secvențe deja parcurse și faci aceeași muncă de mai multe ori.

Tot în familia „nu sorta degeaba" intră și minimul sau maximul: dacă ai nevoie doar de cea mai mică valoare, o parcurgere e de ajuns — sortarea întregului vector e o risipă.

Probleme: cea mai lungă secvență alfabetică · minimul cu linia și maximul cu coloana

Greșeli care se repetă

• Interschimbarea valorii fără cheie — cel mai frecvent bug al capitolului. Rezultatul pare aproape corect, deci trece de verificarea superficială.
• Lipsa parantezelor la criteriul dublu — a || b && c nu înseamnă (a || b) && c.
• j = i în loc de j = i + 1 în bucla interioară — elementul se compară cu el însuși; inofensiv, dar semn de neatenție.
• < în loc de > pentru descrescător — se citește de două ori în ce ordine cere enunțul.
• Sortarea unui vector de care ai nevoie și în ordinea inițială — dacă enunțul cere și poziția originală, păstrează o copie sau sortează un vector de indici.
• Eliminarea duplicatelor înainte de sortare — valorile egale nu sunt încă alăturate, deci comparația cu vecinul nu le prinde.
• Recalcularea cheii la fiecare comparație — corect, dar de zeci de ori mai lent; la n = 10000 se simte.
• float comparat cu == la fracții sau medii — erorile de reprezentare fac ca două valori egale matematic să difere. Pentru egalitate, compară cu o toleranță mică.

Unde exersezi mai departe

Sortarea se învață prin repetiție: tiparul e mereu același, criteriul e mereu altul.

Pentru asta, pbinfo.ro e cea mai bună resursă românească: peste 2500 de probleme de informatică cu evaluator automat, și o trimiți la testat direct din browser. E construită pentru olimpiadă și bacalaureat, deci se completează cu ce găsești aici — noi acoperim subiectele de atestat, cu rezolvări scrise.

Toate problemele din această categorie

Fiecare are rezolvare completă în C++, explicată pas cu pas.