De ce contează?
Joci cărți. Ridici câte o carte și o inserezi în mâna ta la locul corect — deplasezi cărțile mai mari spre dreapta pentru a face loc. La final, cărțile din mână sunt sortate. Asta e sortarea prin inserție.
Algoritmul
La fiecare pas i (de la 1 la n-1):
- Salvăm
cheie = v[i]— elementul de inserat. - Deplasăm spre dreapta elementele din
v[0..i-1]care sunt mai mari decâtcheie. - Inserăm
cheieîn golul creat.
Urmărire pe v = {5, 3, 8, 1, 9}:
Pas 1: cheie=3 | 5>3 → depl → {3, 5, 8, 1, 9}
Pas 2: cheie=8 | 5<8 → stop → {3, 5, 8, 1, 9}
Pas 3: cheie=1 | 8>1, 5>1, 3>1 → depl → {1, 3, 5, 8, 9}
Pas 4: cheie=9 | 8<9 → stop → {1, 3, 5, 8, 9}Zona sortată crește de la stânga. Fiecare element nou „se strecoară" la stânga până găsește un element mai mic sau egal.
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 = 1; i < n; i++) {
int cheie = v[i];
int j = i - 1;
while (j >= 0 && v[j] > cheie) {
v[j + 1] = v[j]; // deplasare la dreapta
j--;
}
v[j + 1] = cheie; // locul corect
}
for (int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Cel mai bun (sortat) | O(n) | O(1) |
| Mediu / Cel mai rău | O(n²) | O(1) |
Sortarea prin inserție e adaptivă: pe date aproape sortate, e mult mai rapidă decât selecția sau bubble sort. Dacă știi că datele vin „aproape ordonate", inserția e alegerea bună dintre sortările pătratice.
Vizualizare
Urmărește zona sortată (stânga) cum crește. La fiecare pas, elementul curent se „strecoară" la stânga până ajunge la locul potrivit, împingând elementele mai mari spre dreapta.
Greșeala 1: v[j] = cheie în loc de v[j + 1] = cheie — scrii cheia cu un index mai mic decât trebuie, suprascriind un element valid.
Greșeala 2: Condiția v[j] >= cheie în loc de v[j] > cheie — deplasezi și elementele egale, sortarea devine instabilă.
Greșeala 3: Uiți j >= 0 în condiția while — dacă cheie e minimul global, j ajunge la -1 și v[-1] e acces invalid.
Recapitulare
- Inserția „strecoară" fiecare element la stânga la locul corect, deplasând elementele mai mari.
- Complexitate O(n²) general, O(n) pe date aproape sortate.
- Sortare stabilă — elementele egale nu-și schimbă ordinea relativă.