Sortarea prin inserție (Insertion Sort) în C++

Sortarea prin inserție (Insertion Sort) în C++

Sortarea prin inserție (Insertion Sort) este o metodă de sortare a vectorilor în complexitate O(n2)O(n^2) oarecum asemănătoare cu sortarea prin selecție. Vom considera că dorim să sortăm crescător vectorul vv de lungime nn indexat de la 11

Algoritm

Sortarea prin inserție presupune că, la fiecare pas i>1i \gt 1 primele i1i - 1 elemente din vector sunt deja sortate. Urmează să extindem această secvență de elemente sortate folosind elementul curent, v[i]v[i] Pentru a vedea pe ce poziție trebuie să-l inserăm pe v[i]v[i] pur și simplu parcurgem elementele de la stânga lui ii căutând unul mai mic sau egal cu v[i]v[i] Dacă notăm poziția la care am găsit acest element cu jj (în caz că nu există un astfel de element, considerăm j=0j = 0 atunci v[i]v[i] va fi inserat pe poziția j+1j + 1 Putem fie să apropiem treptat elementul v[i]v[i] de poziția căutată, interschimbând la fiecare pas elementele v[j]v[j] și v[j1]v[j - 1] ca mai jos…

for (int i = 2; i <= n; i++)
for (int j = i; j > 1 && v[j - 1] > v[j]; j--) {
int aux = v[j];
v[j] = v[j - 1];
v[j - 1] = aux;
}

Fie să mutăm elementele mai mari decât v[i]v[i] cu o poziție la dreapta, în timp ce le parcurgem, urmând ca la final să-l copiem pe v[i]v[i] pe poziția jj Pentru asta vom avea nevoie de o variabilă auxiliară auxaux unde să-l copiem la început pe v[i]v[i] Varianta aceasta este mai eficientă, efectuând de 33 ori mai puține atribuiri.

for (int i = 2; i <= n; i++) {
int j, aux = v[i];
for (j = i; j > 1 && v[j - 1] > aux; j--)
v[j] = v[j - 1];
v[j] = aux;
}

Exemplu

Iată mai jos o vizualizare a algoritmului. Am colorat cu roșu elementul v[i]v[i] cu galben v[j]v[j] cu verde elementele sortate și cu alb pe celelalte.

Complexitate

Primul for efectuează O(n)O(n) iterații, iar al doilea, în cel mai rău caz, tot O(n)O(n) Prin urmare, complexitatea în timp a sortării prin inserție este O(n2)O(n^2) Cel mai rău caz este atins atunci când vectorul dat este sortat invers (descrescător). Cel mai bun caz, în care algoritmul rulează în O(n)O(n) este cel în care vectorul e deja sortat.

Având în vedere că elementele de la stânga lui ii sunt sortate, putem căuta binar poziția jj la care trebuie să-l inserăm pe v[i]v[i] Astfel, am reduce numărul de comparații de la fiecare pas de la O(n)O(n) la O(logn)O(\log n) Totuși, optimizarea asta nu schimbă complexitatea finală, pentru că oricum mutarea elementelor la dreapta consumă O(n)O(n) operații.

Dacă aveți vreo întrebare legată de sortarea prin inserție în C++, nu ezitați să o lăsați mai jos, într-un comentariu

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii