Sortarea prin inserție

Sortarea prin inserție păstrează un prefix sortat și introduce următoarea valoare în locul potrivit din acel prefix. Din $[5,2,4]$, introducem 2 înainte de 5 și obținem $[2,5,4]$; apoi introducem 4 între 2 și 5, rezultând $[2,4,5]$.

Sortarea prin inserție păstrează în stânga un prefix sortat, inițial formată din primul element. La pasul $i$ se ia elementul x = v[i], se deplasează cu o poziție spre dreapta elementele din prefix care sunt mai mari decât x, iar x se scrie în locul rămas liber. După pasul $i$, prefixul de lungime $i+1$ este sortat. Numărul de deplasări este egal cu numărul inversiunilor șirului. Pe un tablou deja sortat se face câte o singură comparație pe pas, deci $n-1$ în total și nicio deplasare; pe un tablou sortat invers se fac $\frac{n(n-1)}{2}$ deplasări. Comparația strictă > oprește deplasarea la un element egal cu x, deci elementele egale își păstrează ordinea: metoda este stabilă. Memoria auxiliară este constantă.

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

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

După fiecare pas tabloul este: 2 5 4 1 3 (2 intră înaintea lui 5), 2 4 5 1 3 (4 intră între 2 și 5), 1 2 4 5 3 (1 trece peste trei elemente și ajunge la început), 1 2 3 4 5 (3 trece peste 5 și 4). Deplasările sunt $1+1+3+2=7$, egale cu numărul inversiunilor. Prefixul sortat crește cu un element la fiecare pas.

Exemplul 2 — cazurile extreme. Pentru $1,2,3,4,5$ (deja sortat), condiția v[j] > x este falsă de la prima comparație, deci se fac 4 comparații și 0 deplasări. Pentru $5,4,3,2,1$ (sortat invers), fiecare element nou trece peste tot prefixul: deplasările sunt $1+2+3+4=10$. Pentru $4,1,3,2$ deplasările sunt 4, numărul inversiunilor $(4;1)$, $(4;3)$, $(4;2)$ și $(3;2)$. Pe date aproape sortate inserția este foarte rapidă, de aceea se folosește adesea pentru prelucrarea finală a unor tablouri parțial ordonate.

Exemplul 3 — inserția unei valori într-un tablou sortat. Pentru a păstra un tablou sortat după adăugarea unei valori se folosește chiar pasul de inserție: din $2,4,7,9$ se adaugă 5, se deplasează 9 și 7 spre dreapta, iar 5 intră pe poziția 2, rezultând $2,4,5,7,9$. Aceeași idee permite menținerea unui tablou sortat pe măsură ce valorile sunt citite, fără o sortare separată la sfârșit.

Diferența se vede la dimensiuni mari. Pentru $n=1000$, un tablou deja sortat cere 999 de comparații, iar unul sortat invers cere $\frac{1000\cdot 999}{2}=499500$ de deplasări. Pentru aceeași dimensiune, un tablou „aproape sortat”, în care fiecare element este la cel mult o poziție de locul lui, cere cel mult câteva sute de deplasări.

Exemplul 4 — stabilitatea pe date cu două câmpuri. Elevii $(7,\text{Ana})$, $(5,\text{Dan})$, $(7,\text{Mara})$ și $(5,\text{Ion})$ se sortează crescător după notă. La $i=1$, Dan intră înaintea Anei. La $i=2$, Mara are nota 7 ca Ana și comparația strictă > este falsă, deci Mara rămâne după Ana. La $i=3$, Ion trece peste Mara și peste Ana, dar se oprește după Dan, pentru că $5>5$ este fals. Rezultatul este Dan, Ion, Ana, Mara, cu trei deplasări: elevii cu aceeași notă și-au păstrat ordinea inițială.

Verifică ordinea condițiilor din j >= 0 && v[j] > x: evaluarea scurtcircuitată împiedică accesul la v[-1]. După deplasări, locul lui x este j + 1, nu j. Prefixul sortat crește cu un element la fiecare iterație. Dacă subiectul cere starea tabloului după $p$ pași, numără pașii exteriori (valorile lui i), nu deplasările. Pe un tablou cu elemente egale, comparația >= în loc de > ar deplasa și elementele egale, deci ar schimba ordinea lor.

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

int a[] = {2, 5, 4, 1, 3};
for (int i = 1; i < 3; i++) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = x;
}
for (int i = 0; i < 5; i++)
    cout << a[i] << ' ';

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

Răspunsul corect este b). Ciclul face doar doi pași. Pentru $i=1$, $x=5$ nu este mai mic decât 2, deci rămâne pe loc. Pentru $i=2$, $x=4$ este mai mic decât 5, deci 5 se deplasează la dreapta, iar 4 intră pe poziția 1: 2 4 5 1 3. Ultimele două elemente nu au fost încă prelucrate. Varianta d) este starea după trei pași, iar varianta a) după toți patru.

Numărarea deplasărilor. Pentru $4,3,2,1$ trei pași exteriori produc, pe rând, tablourile $3,4,2,1$ (o deplasare), $2,3,4,1$ (două deplasări) și $1,2,3,4$ (trei deplasări), în total $1+2+3=6$. Pentru $3,1,2,5,4$ se fac trei deplasări: la $i=1$ valoarea 1 mută pe 3, la $i=2$ valoarea 2 mută tot pe 3, la $i=3$ valoarea 5 nu mută nimic, iar la $i=4$ valoarea 4 mută pe 5. Dacă ți se cere numărul de atribuiri a[j + 1] = a[j], numără doar deplasările, nu și scrierile finale a[j + 1] = x.

Greșeli frecvente

• Greșit: după deplasări, valoarea x se scrie la v[j].
  Corect: se scrie la v[j + 1], locul rămas liber.
• Greșit: inserția face mereu $n(n-1)/2$ comparații.
  Corect: pe date sortate face doar $n-1$.
• Greșit: dacă ordinea condițiilor se inversează în v[j] > x && j >= 0, rezultatul este același.
  Corect: se poate accesa v[-1], în afara tabloului.

Înainte și după