Metode elementare de sortare

Sortarea prin selecție, prin interschimbare și prin inserție, plus sortarea prin numărare. Cum funcționează și când o alegi pe fiecare.

Ce înseamnă a sorta

Înseamnă să aranjezi elementele unui vector în ordine crescătoare (sau descrescătoare). Pare simplu și chiar este, dar metoda aleasă schimbă mult timpul de execuție.

Toate metodele de mai jos au nevoie de interschimbarea a două elemente:

int aux = v[i];
v[i] = v[j];
v[j] = aux;

Trei atribuiri, în ordinea asta. Fără variabila auxiliară, prima atribuire distruge valoarea de care ai nevoie la a doua. În pseudocod există notația directă v[i] ↔ v[j].

Sortarea prin selecție

Ideea: caut cel mai mic element din tot vectorul și îl aduc pe prima poziție. Apoi caut cel mai mic din ce a rămas și îl aduc pe a doua. Și tot așa.

for (int i = 1; i < n; i++) {
    int p = i;
    for (int j = i + 1; j <= n; j++)
        if (v[j] < v[p])
            p = j;
    if (p != i) {
        int aux = v[i]; v[i] = v[p]; v[p] = aux;
    }
}

Bucla exterioară merge până la n-1, nu la n. După ce primele n-1 elemente sunt la locul lor, ultimul e sigur și el la locul lui.

Face mereu aproximativ n²/2 comparații, dar cel mult n interschimbări. Sunt puține, așa că metoda e utilă când mutarea elementelor e costisitoare.

Sortarea prin interschimbare

Ideea: compar vecini și îi interschimb dacă sunt în ordine greșită. Repet până când o parcurgere întreagă nu mai face nicio interschimbare.

bool schimbat;
do {
    schimbat = false;
    for (int i = 1; i < n; i++)
        if (v[i] > v[i+1]) {
            int aux = v[i]; v[i] = v[i+1]; v[i+1] = aux;
            schimbat = true;
        }
} while (schimbat);

Indicatorul schimbat contează: fără el ai face mereu n parcurgeri, chiar dacă vectorul s-a sortat de la a doua. Cu el, un vector deja sortat este confirmat într-o singură trecere.

La fiecare parcurgere, cel mai mare element rămas urcă la coadă. De aceea metoda se mai numește și „a bulelor".

Sortarea prin inserție

Ideea: consider primele i elemente deja sortate și îl inserez pe al i+1-lea la locul lui între ele, împingând spre dreapta elementele mai mari.

for (int i = 2; i <= n; i++) {
    int x = v[i], j = i - 1;
    while (j >= 1 && v[j] > x) {
        v[j+1] = v[j];
        j--;
    }
    v[j+1] = x;
}

Așa aranjează un om cărțile de joc în mână.

Are o proprietate utilă: pe un vector aproape sortat face foarte puțină muncă, pentru că bucla interioară se oprește imediat. În acest caz e cea mai rapidă dintre cele trei.

Cât costă

Toate trei sunt de ordinul n². Pentru n = 1000 înseamnă un milion de operații, adică practic instantaneu. Pentru n = 100000 sunt zece miliarde, mult prea mult.

Pentru examen: metodele elementare sunt suficiente pentru limitele obișnuite de la bac, unde n este de ordinul miilor. Dacă un enunț dă n = 10⁵ sau mai mult, îți trebuie altă abordare.

Sortarea prin numărare

Când valorile sunt întregi, nenegative și mărginite, poți sorta fără nicio comparație, folosind vectorul de frecvențe:

int fr[1001] = {0};
for (int i = 1; i <= n; i++)
    fr[v[i]]++;

int k = 0;
for (int x = 0; x <= 1000; x++)
    while (fr[x] > 0) {
        v[++k] = x;
        fr[x]--;
    }

Costul este n + V, unde V este valoarea maximă, deci practic liniar. E de departe cea mai rapidă metodă când se poate aplica. Condițiile sunt aceleași ca la orice vector de frecvențe: valori întregi, nenegative, cu limită mică.

Pentru un vector de un milion de note între 1 și 10, e alegerea evidentă. Pentru valori de ordinul miliardelor, nu se poate folosi.

Sortare descrescătoare

Se schimbă un singur semn de comparație. La inserție, v[j] > x devine v[j] < x. La interschimbare, v[i] > v[i+1] devine v[i] < v[i+1].

Sortarea după alt criteriu

Criteriul de comparație nu trebuie să fie valoarea însăși:

// sortez crescător după suma cifrelor
if (sumaCifrelor(v[i]) > sumaCifrelor(v[i+1])) { /* interschimb */ }

Structura algoritmului rămâne identică. Se schimbă doar întrebarea „care dintre două este mai mic". Tocmai de aceea merită să înțelegi metodele, în loc să le memorezi.

De reținut

• Interschimbarea are nevoie de variabilă auxiliară, în trei atribuiri.
• Selecție: caut minimul și îl aduc în față. Puține mutări.
• Interschimbare: compar vecini, cu indicator care oprește devreme.
• Inserție: inserez în partea deja sortată. Foarte rapidă pe date aproape sortate.
• Toate trei costă ~n² și ajung pentru n de ordinul miilor.
• Sortarea prin numărare este liniară, dar cere valori întregi mărginite.