Sortarea prin selecție

Sortarea prin selecție fixează pe rând fiecare poziție. Pentru poziția curentă, caută minimul în partea încă nesortată și îl schimbă cu elementul de pe poziția curentă. Din $[5,2,4]$, selectează 2 și obține $[2,5,4]$; apoi selectează 4 și obține $[2,4,5]$.

În Python, min([5,2,4]) găsește 2, valoarea aleasă pentru prima poziție a sortării prin selecție.

Sortarea prin selecție construiește rezultatul de la stânga la dreapta. La pasul $i$, partea din stânga, de la poziția 0 la $i-1$, este deja sortată și conține cele mai mici $i$ valori. În partea rămasă se caută minimul și poziția lui k, apoi acest minim se schimbă cu elementul de pe poziția $i$. După $n-1$ pași tabloul este sortat; ultimul element ajunge de la sine pe locul lui. Căutarea minimului cere $n-1-i$ comparații la pasul $i$, deci în total $(n-1)+(n-2)+\dots +1=\frac{n(n-1)}{2}$ comparații, indiferent de ordinea inițială. Numărul de schimburi este cel mult $n-1$, mai mic decât la alte metode simple. Memoria auxiliară este constantă. Cu schimbul simplu, metoda nu este stabilă.

Exemplul 1 — tabloul $5,2,4,1,3$.

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

După fiecare pas, tabloul este: 1 2 4 5 3 (minimul 1 de pe poziția 3 se schimbă cu 5), apoi 1 2 4 5 3 (minimul 2 este deja pe poziția 1, schimbul nu modifică nimic), apoi 1 2 3 5 4 (minimul 3 de pe poziția 4 se schimbă cu 4) și în final 1 2 3 4 5. Comparațiile sunt $4+3+2+1=10$, iar schimburile care mută efectiv un element sunt 3. Prefixul sortat crește cu un element la fiecare pas.

Exemplul 2 — varianta în Python și ordinea descrescătoare. Poziția minimului din secvența rămasă se obține cu min(range(i, n), key=lambda t: v[t]). Pentru ordine descrescătoare se caută maximul, iar comparația v[j] < v[k] devine v[j] > v[k]. Pentru $[5,2,4]$ în ordine descrescătoare rezultă $[5,4,2]$: la $i=0$ maximul 5 este deja pe loc, la $i=1$ maximul 4 se schimbă cu 2.

v = [5, 2, 4]
n = len(v)
for i in range(n - 1):
    k = max(range(i, n), key=lambda t: v[t])
    v[i], v[k] = v[k], v[i]
print(v)

Programul afișează [5, 4, 2]. Atribuirea v[i], v[k] = v[k], v[i] schimbă valorile fără variabilă ajutătoare.

Exemplul 3 — instabilitatea. Fie elementele $2_a$, $2_b$ și $1$, în această ordine, sortate crescător după valoare. La primul pas minimul 1, aflat pe poziția 2, se schimbă cu $2_a$ de pe poziția 0: rezultă $1,2_b,2_a$. Elementele egale și-au inversat ordinea relativă. Dacă ele au și alte câmpuri, rezultatul poate fi nedorit; când ordinea lor contează, se alege o metodă stabilă, de pildă inserția. Pentru $n=1000$ selecția face 499 500 de comparații, dar cel mult 999 de schimburi.

Invariantul și cazul unui tablou descrescător. Invariantul sortării prin selecție este: înaintea pasului $i$, primele $i$ poziții conțin cele mai mici $i$ valori ale tabloului, în ordine crescătoare. De aceea ciclul exterior nu revine niciodată asupra lor și se oprește la $i=n-2$. Pentru tabloul descrescător $[4,3,2,1]$, stările după cei trei pași sunt 1 3 2 4, 1 2 3 4 și 1 2 3 4. La ultimul pas minimul 3 se află deja pe poziția 2, deci schimbul nu modifică tabloul. Comparațiile sunt $3+2+1=6$, la fel ca pentru orice alt tablou cu patru elemente, dar schimburile efective sunt doar 2. Numărul comparațiilor nu depinde de date, iar cel al schimburilor depinde, fără să depășească $n-1$.

Urmărește indicele minimului, nu doar valoarea lui. La fiecare iterație exterioară, partea din stânga este deja sortată și nu mai intră în căutarea minimului. Dacă bucla interioară începe la j = i în loc de i + 1, comparația suplimentară a elementului cu el însuși nu schimbă rezultatul, dar dacă începe mai târziu poate rata minimul. Când un subiect cere starea tabloului după $p$ iterații, oprește urmărirea după exact $p$ schimburi, nu după $p$ comparații.

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

int v[] = {4, 3, 5, 1, 2};
for (int i = 0; i < 2; i++) {
    int k = i;
    for (int j = i + 1; j < 5; j++)
        if (v[j] < v[k]) k = j;
    swap(v[i], v[k]);
}
for (int i = 0; i < 5; i++)
    cout << v[i] << ' ';

• a) 1 2 3 4 5
• b) 1 2 5 4 3
• c) 1 3 5 4 2
• d) 3 4 5 1 2

Răspunsul corect este b). Ciclul exterior face doar două iterații. Pentru $i=0$ minimul 1 de pe poziția 3 se schimbă cu 4: 1 3 5 4 2. Pentru $i=1$ minimul din restul tabloului este 2, de pe poziția 4, și se schimbă cu 3: 1 2 5 4 3. Restul tabloului rămâne nesortat. Varianta a) ar fi rezultatul după toate cele patru iterații, iar varianta c) este starea după prima iterație.

Al doilea exemplu — numărul de schimburi efective. Ce valoare are $k$ la sfârșitul secvenței?

int v[] = {6, 2, 5, 1}, k = 0;
for (int i = 0; i < 3; i++) {
    int m = i;
    for (int j = i + 1; j < 4; j++)
        if (v[j] < v[m]) m = j;
    if (m != i) { swap(v[i], v[m]); k++; }
}
cout << k;

La $i=0$ minimul 1 se află pe poziția 3 și se schimbă cu 6: 1 2 5 6, iar $k=1$. La $i=1$ și $i=2$ minimul se află chiar pe poziția curentă, deci $m=i$ și nu se mai schimbă nimic. Se afișează 1. Verifică și condiția ciclului exterior: pentru patru elemente, i < 3 este suficient, pentru că ultimul element ajunge de la sine pe locul lui.

Greșeli frecvente

• Greșit: la fiecare pas se schimbă primul element cu al doilea, dacă sunt în ordine greșită.
  Corect: se caută minimul din partea nesortată și se schimbă cu elementul de pe poziția curentă.
• Greșit: selecția face mai puține comparații pe date deja sortate.
  Corect: face același număr, $n(n-1)/2$.
• Greșit: sortarea prin selecție cu schimb simplu păstrează ordinea elementelor egale.
  Corect: nu este stabilă în general.

Înainte și după