De ce contează?
Trebuie să aranjezi cărțile de pe masă după număr. Cel mai simplu mod: cauți cea mai mică, o pui prima. Cauți cea mai mică din ce rămâne, o pui pe locul doi. Repeți. La fiecare pas, plasezi definitiv un element.
Algoritmul
La fiecare pas i (de la 0 la n-2):
- Găsim minimul din subvectorul
v[i..n-1]. - Interschimbăm minimul cu
v[i].
Urmărire pe v = {5, 3, 8, 1, 9}:
Pas 0: min in [5,3,8,1,9] = 1 la poz 3 → swap v[0]↔v[3] → {1, 3, 8, 5, 9}
Pas 1: min in [3,8,5,9] = 3 la poz 1 → swap v[1]↔v[1] → {1, 3, 8, 5, 9}
Pas 2: min in [8,5,9] = 5 la poz 3 → swap v[2]↔v[3] → {1, 3, 5, 8, 9}
Pas 3: min in [8,9] = 8 la poz 3 → swap v[3]↔v[3] → {1, 3, 5, 8, 9}
Sortat!La fiecare pas, zona sortată (stânga) crește cu un element. Minimul găsit în zona nesortată ajunge definitiv pe locul lui.
Implementare C++
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int v[1001];
for (int i = 0; i < n; i++) cin >> v[i];
for (int i = 0; i < n - 1; i++) {
int poz_min = i;
for (int j = i + 1; j < n; j++) {
if (v[j] < v[poz_min]) poz_min = j;
}
int t = v[i]; v[i] = v[poz_min]; v[poz_min] = t;
}
for (int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Orice caz | O(n²) | O(1) |
Sortarea prin selecție face întotdeauna O(n²) comparații — chiar dacă vectorul e deja sortat. Avantajul: exact n-1 swap-uri, mai puțin decât alte sortări pătratice. Util când operația de schimb e costisitoare.
Vizualizare
Urmărește cum zona sortată (stânga) crește cu câte un element la fiecare pas. Elementul evidențiat e minimul din zona nesortată care se mută pe locul corect.
Greșeala 1: poz_min = 0 în loc de poz_min = i la inițializare — cauți minimul din tot vectorul la fiecare pas, nu din zona nesortată. Elementele deja sortate pot fi re-selectate greșit.
Greșeala 2: Swap fără variabilă temporară: v[i] = v[poz_min]; v[poz_min] = v[i]; — suprascrii v[i] înainte de a-l salva.
Greșeala 3: Bucla exterioară merge până la i < n în loc de i < n-1 — ultimul pas e inutil (un singur element nu necesită sortare). Nu strică corectitudinea, dar adaugă un ciclu.
Recapitulare
- La fiecare pas, găsim minimul din zona nesortată și îl punem pe locul corespunzător.
- Complexitate O(n²) timp, O(1) spațiu, exact n-1 swap-uri.
- Folosit la concursuri doar pentru n ≤ 5.000.