Noțiunea de sortare

Sortarea rearanjează elementele după o relație de ordine, de obicei crescător sau descrescător. Din $[5,2,4]$ obținem $[2,4,5]$ crescător. Numărul de elemente și valorile, inclusiv repetițiile, se păstrează; se schimbă doar ordinea. Lecțiile „Sortarea prin selecție”, „Sortarea prin metoda bulelor”, „Sortarea prin inserție”, „Sortarea prin numărare”, „Sortarea rapidă” și „Sortarea prin interclasare” arată metode diferite.

În Python, sorted([5,2,4]) produce lista nouă [2,4,5]. La studierea unui algoritm de sortare urmărești și pașii intermediari, nu numai rezultatul.

Sortarea rearanjează o colecție după o cheie și o ordine, păstrând inclusiv repetițiile. O sortare corectă respectă ordinea cerută și nu pierde elemente. Metodele diferă prin comparații, mutări, memorie suplimentară și comportamentul pe date deja ordonate. O metodă stabilă păstrează ordinea relativă a elementelor cu aceeași cheie, utilă când acestea au și alte câmpuri.

Metoda bulelor

Metoda bulelor interschimbă vecinii dezordonați; după prima trecere, maximul ajunge la final. O variabilă pentru interschimbări permite oprirea când vectorul este sortat. Trecerile pas cu pas, numărul de interschimbări și sortarea după un criteriu sunt în lecția despre bubble sort.

Sortarea prin selecție

Pentru fiecare poziție i, de la prima la penultima, cauți minimul dintre elementele de la i până la final și îl interschimbi cu elementul de pe poziția i. Numărul de comparații este mereu același, dar interschimbările sunt cel mult n − 1, ceea ce o face utilă când mutarea unui element costă mult. Exemplul de mai jos o aplică pas cu pas.

Sortarea prin inserție

Partea din stânga a vectorului este mereu sortată. Iei următorul element, muți spre dreapta elementele mai mari decât el și îl pui pe locul rămas liber, ca atunci când aranjezi cărțile de joc în mână. Pe un vector aproape sortat face foarte puține mutări.

Sortarea prin numărare

Când valorile sunt numere naturale mici (de exemplu, note sau cifre), folosești un vector de frecvență: f[v] reține de câte ori apare valoarea v. Apoi parcurgi valorile posibile în ordine și scrii fiecare valoare de câte ori a apărut. Metoda nu compară elemente între ele, dar are nevoie de un vector cât valoarea maximă.

Sortarea rapidă și sortarea prin interclasare

Ambele sunt aplicații ale metodei divide et impera, din clasa a XI-a. Sortarea rapidă alege un pivot, așază la stânga lui valorile mai mici și la dreapta pe cele mai mari, apoi sortează cele două părți; detaliile sunt în lecția despre quicksort. Sortarea prin interclasare împarte vectorul în două jumătăți, le sortează și le unește într-un singur vector ordonat. Interclasarea a doi vectori deja sortați apare și singură în programa de Bacalaureat.

Un fragment care nu este algoritm de sortare

O metodă simplă compară și schimbă două elemente aflate în ordine greșită:

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int v[] = {5, 2, 4};
    if (v[0] > v[1]) swap(v[0], v[1]);
    if (v[1] > v[2]) swap(v[1], v[2]);
    for (int x : v) cout << x << ' ';
    return 0;
}

Programul afișează 2 4 5, dar nu este un algoritm de sortare: pentru $[4,5,2]$ ar da $[4,2,5]$, adică un șir nesortat. O sortare corectă garantează ordinea pentru toate intrările permise, nu doar pentru un exemplu.

Exemplul 2 — compararea metodelor pe același tablou. Pentru $[5,2,4,1,3]$, sortarea prin selecție face 10 comparații și 3 schimburi, metoda bulelor face 10 comparații și 7 schimburi, iar sortarea prin inserție face 7 deplasări de elemente. Numărul de schimburi ale metodei bulelor și numărul de deplasări ale inserției sunt egale cu numărul de inversiuni ale șirului, adică al perechilor aflate în ordine greșită: $(5,2)$, $(5,4)$, $(5,1)$, $(5,3)$, $(2,1)$, $(4,1)$ și $(4,3)$, în total 7. Pe un tablou deja sortat inserția face doar $n-1$ comparații și nicio deplasare, pe când selecția face tot $n(n-1)/2$ comparații.

Alegerea unei metode depinde de datele problemei. Pentru tablouri mici și simple se folosește una dintre metodele cu $n^2$ pași; pentru tablouri mari se preferă metodele rapide (sortarea rapidă și sortarea prin interclasare, cu $n\log n$ pași), iar pentru valori întregi dintr-un interval mic, sortarea prin numărare, cu $n+R-L+1$ pași.

Exemplul 3 — stabilitatea. Elementele $7_a$, $9$, $7_b$ se ordonează crescător după valoare. O metodă stabilă dă $7_a,7_b,9$, adică cele două elemente egale rămân în ordinea inițială. Sortarea prin selecție cu schimb simplu poate da $7_b,7_a,9$ pentru șirul $7_a,7_b,3$: minimul 3 este schimbat cu primul element, iar $7_a$ ajunge după $7_b$. În Python, sorted și list.sort sunt stabile.

elevi = [(7, "Ana"), (9, "Bia"), (7, "Cora")]
print(sorted(elevi, key=lambda e: e[0]))

Programul afișează [(7, 'Ana'), (7, 'Cora'), (9, 'Bia')]: Ana rămâne înaintea Corei, deși au aceeași notă.

Exemplul 4 — sortarea prin numărare. Pentru șirul $3,1,3,0,1$, cu valori întregi între 0 și 3, se numără de câte ori apare fiecare valoare: vectorul de frecvențe este $(1,2,0,2)$, pentru valorile 0, 1, 2 și 3. Apoi fiecare valoare se scrie de atâtea ori cât arată frecvența ei: 0 o dată, 1 de două ori, 2 niciodată, 3 de două ori. Rezultatul este $0,1,1,3,3$. Metoda nu compară elementele între ele și face aproximativ $n+(R-L+1)=5+4=9$ pași, dar are sens numai dacă domeniul valorilor este mic.

Exemple rezolvate

Exemplul 1: sortarea prin selecție, pas cu pas

Sortează crescător vectorul 7, 3, 9, 1, 5 prin selecția minimului și afișează vectorul după fiecare pas.

1. Pasul 1: minimul dintre toate cele cinci valori este 1, pe poziția a patra; îl interschimbi cu 7: 1, 3, 9, 7, 5.
2. Pasul 2: minimul dintre 3, 9, 7, 5 este 3, deja pe locul lui: vectorul nu se schimbă.
3. Pasul 3: minimul dintre 9, 7, 5 este 5; îl interschimbi cu 9: 1, 3, 5, 7, 9.
4. Pasul 4: minimul dintre 7 și 9 este 7, deja pe locul lui.

#include <iostream>
using namespace std;

int main() {
    int v[] = {7, 3, 9, 1, 5}, n = 5;
    for (int i = 0; i < n - 1; i++) {
        int pmin = i;                       // pozitia minimului din v[i..n-1]
        for (int j = i + 1; j < n; j++)
            if (v[j] < v[pmin])
                pmin = j;
        int aux = v[i]; v[i] = v[pmin]; v[pmin] = aux;
        for (int k = 0; k < n; k++)
            cout << v[k] << " ";
        cout << "\n";
    }
    return 0;
}

Programul afișează:

1 3 9 7 5
1 3 9 7 5
1 3 5 7 9
1 3 5 7 9

Pentru n = 5 elemente, selecția face 4 + 3 + 2 + 1 = 10 comparații, adică $\frac{5\cdot 4}{2}$, oricum ar fi așezate valorile la început.

La un item de examen, stabilește cheia, sensul ordonării și metoda cerută. Dacă enunțul dă pașii sortării prin selecție, inserție sau interschimbare, urmărește exact acei pași; rezultatul final singur nu răspunde la o întrebare despre o etapă intermediară. De exemplu, pentru $7;2;7;1$, ordonarea crescătoare dă $1;2;7;7$, dar după prima trecere a sortării prin selecție primul element este minimul 1 schimbat cu $7$, deci șirul este $1;2;7;7$, iar după prima trecere a metodei bulelor este $2;7;1;7$. Selecția face $n(n-1)/2$ comparații indiferent de ordinea inițială, iar inserția pe un tablou deja sortat face $n-1$ comparații. Dacă elementele cu aceeași cheie trebuie să își păstreze ordinea relativă, folosește o metodă stabilă.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int c = 0;
for (int i = 0; i < 5; i++)
    for (int j = i + 1; j < 6; j++)
        c++;
cout << c;

• a) 5
• b) 6
• c) 15
• d) 30

Răspunsul corect este c). Ciclurile parcurg toate perechile de poziții $(i,j)$ cu $i<j$ dintr-un tablou cu 6 elemente: pentru $i=0$ sunt 5 valori ale lui $j$, pentru $i=1$ sunt 4, apoi 3, 2 și 1. Suma este $5+4+3+2+1=15=\frac{6\cdot 5}{2}$. Este exact numărul de comparații al sortării prin selecție pentru $n=6$. Varianta d) numără toate perechile ordonate, iar varianta a) numără numai primul ciclu exterior.

La metoda bulelor, după prima trecere cel mai mare element ajunge pe ultima poziție: din $4;3;2;1$ se obține $3;2;1;4$, iar după $i$ treceri ultimele $i$ elemente sunt deja la locul lor.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: la „Algoritmi elementari”, programa de examen numește metodele de ordonare (metoda bulelor, a inserției, a selecției și a numărării), interclasarea, metodele de căutare și analiza complexității unui algoritm; sortarea rapidă și sortarea prin interclasare nu sunt numite (programa de examen, anexa 2 la OMECTS 4800/2010). În programa școlară veche de clasa a XI-a, ele apar ca exemple de aplicații ale metodei divide et impera (programa de clasa a XI-a).

Greșeli frecvente

• Greșit: două comparații și schimburi pot sorta orice tablou cu trei elemente.
  Corect: un algoritm de sortare trebuie să funcționeze pentru toate intrările permise.
• Greșit: sortarea poate șterge elementele repetate.
  Corect: păstrează toate elementele, inclusiv repetițiile; se schimbă doar ordinea.
• Greșit: toate metodele de sortare fac același număr de comparații.
  Corect: selecția face mereu $n(n-1)/2$, iar inserția poate face doar $n-1$ pe date sortate.
• Greșit: sortarea crescătoare a lui $[5,2,4]$ este $[5,4,2]$.
  Corect: aceasta este descrescătoare.

Înainte și după

Întrebări frecvente