Sortarea prin selecție și sortarea prin inserție

Pe lângă metoda bulelor, programa de BAC informatică include încă două sortări clasice: sortarea prin selecție și sortarea prin inserție. Amândouă ordonează un vector în timp pătratic, dar o fac în moduri foarte diferite — iar itemii de la examen testează exact diferența: „ce conține vectorul după al doilea pas?”, „câte comparații se fac?”, „completați secvența lipsă”. Mai jos le iei pe rând, pe același vector, ca să le poți compara direct.

Sortarea prin selecție

Ideea: la pasul i, selectezi cel mai mic element din porțiunea v[i], v[i+1], …, v[n] și îl aduci pe poziția i printr-o interschimbare. După pasul 1, minimul întregului vector e pe poziția 1; după pasul 2, al doilea cel mai mic e pe poziția 2 și așa mai departe. După n−1 pași, vectorul e sortat.

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

Urmărire pe vectorul 4 2 5 1:

Numărul de comparații între elemente este 3 + 2 + 1 = 6. În general, sortarea prin selecție face întotdeauna n(n−1)/2 comparații, indiferent cum arată vectorul la început — chiar dacă e deja sortat. În schimb, face cel mult n−1 interschimbări, câte una pe pas.

Varianta „prin interschimbare directă”

În multe manuale și subiecte apare o variantă mai scurtă, fără variabila pmin: compari v[i] cu fiecare v[j] de după el și interschimbi imediat ce găsești un element mai mic.

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

Rezultatul final e același, iar după fiecare pas i, pe poziția i se află tot minimul porțiunii. Diferența apare la conținutul intermediar al vectorului, pentru că se fac mai multe interschimbări. Pe 4 2 5 1, la pasul i = 1: 2 < 4 → 2 4 5 1; 5 nu e mai mic decât 2; 1 < 2 → 1 4 5 2. Compară cu varianta clasică, unde după pasul 1 vectorul era 1 2 5 4. De aceea, la un item de urmărire, folosește exact codul din enunț.

Sortarea prin inserție

Ideea seamănă cu felul în care îți aranjezi cărțile de joc în mână: porțiunea v[1..i−1] este deja sortată, iar elementul v[i] trebuie inserat la locul lui în ea. Îl salvezi într-o variabilă x, muți spre dreapta toate elementele sortate mai mari decât x și pui x în locul eliberat.

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

Urmărire pe același vector, 4 2 5 1:

Total: 5 comparații între elemente, față de 6 la selecție. Diferența devine mare pe vectori aproape sortați: dacă vectorul e deja ordonat crescător, fiecare pas face o singură comparație, deci n−1 comparații în total. În cel mai rău caz (vector ordonat descrescător), elementul nou trebuie dus de fiecare dată până la început, iar numărul de comparații ajunge la n(n−1)/2.

Detaliu important în condiția buclei: j >= 1 && v[j] > x. Ordinea contează — dacă j a ajuns la 0, prima condiție e falsă și a doua nu se mai evaluează, deci nu accesezi un element din afara vectorului. Iar la final, x se pune pe poziția j + 1, nu j.

Pseudocodul sortării prin inserție

pentru i ← 2, n execută
    x ← v[i]
    j ← i - 1
    cât timp j ≥ 1 și v[j] > x execută
        v[j+1] ← v[j]
        j ← j - 1
    v[j+1] ← x

Comparație directă

Prima linie a tabelului e cea mai utilă la itemii de urmărire. După doi pași de selecție pe 4 2 5 1, primele două elemente sunt 1 și 2 — minimele întregului vector. După doi pași de inserție, primele trei elemente sunt 2 4 5, sortate, dar 1 încă nu a ajuns pe prima poziție.

Pe care o folosești în program?

Când trebuie doar să sortezi un vector mic într-un program de la Subiectul III, oricare dintre metode e acceptată, așa că alege-o pe cea pe care o scrii fără greșeală. Pentru sortarea descrescătoare schimbi doar comparațiile: v[j] > v[pmin] la selecție, v[j] < x la inserție. Amintește-ți însă că ambele sunt O(n²): la problema de eficiență, cu un milion de valori, nu sunt soluția potrivită.