Analiza sortării prin inserție

Ca și sortarea prin selecție, sortarea prin inserție parcurge în mod repetat indicii vectorului, apelând insert pentru elementele de pe pozițiile $1,2,3,\dots ,n-1$‍. Atât apelul către indexOfMinimum, cât și apelul către insert au un timp de execuție care depinde de dimensiunea subșirului sortat. De fapt, cuvântul „au” din propoziția precedentă ar trebui transformat în „pot avea” și vom vedea în continuare de ce.

Să alegem un caz în care apelăm insert, iar valoarea care trebuie inserată în subșir este mai mică decât toate elementele din subșir. De exemplu, dacă inserăm valoarea 0 în subșirul [2, 3, 5, 7, 11], atunci fiecare element din subșir trebuie deplasat cu o poziție la dreapta. Așadar, în general, dacă inserăm într-un subșir cu $k$‍ elemente, am putea fi nevoiți să le deplasăm cu o poziție la dreapta pe toate cele $k$‍. În loc să numărăm de câte instrucțiuni avem nevoie pentru a compara un element cu cheia și pentru a deplasa elementul respectiv, haide să fim de acord că este un număr constant de instrucțiuni; să denumim această constantă $c$‍. Așadar, ar putea fi nevoie de $c\cdot k$‍ instrucțiuni pentru a insera o valoare într-un subșir de $k$‍ elemente.

Să presupunem că la fiecare apel către insert, valoarea care trebuie inserată este mai mică decât toate elementele din subșirul din stânga sa. Atunci când apelăm insert pentru prima dată, $k=1$‍. A doua oară, $k=2$‍. A treia oară, $k=3$‍. Și așa mai departe până la ultimul apel, când $k=n-1$‍. Așadar, timpul de execuție al inserării într-un subșir sortat este

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

Această sumă este o progresie aritmetică, cu ultimul termen egal cu $n-1$‍ în loc de $n$‍. Folosind formula de calcul pentru progresii aritmetice, obținem că timpul de execuție al inserării într-un subșir sortat este

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

Folosind notația Θ, renunțăm la termenul de ordin mai mic $cn/2$‍ și la constantele $c$‍ și 1/2 și obținem că timpul de execuție al sortării prin inserție este, în acest caz, $\mathrm{\Theta }(n^2)$‍.

Putem obține un timp mai mic decât $\mathrm{\Theta }(n^2)$‍ la sortarea prin inserție? Răspunsul este afirmativ. Să presupunem că avem vectorul [2, 3, 5, 7, 11], în care subșirul sortat conține primele 4 elemente și urmează să inserăm valoarea 11. La prima verificare, observăm că 11 este mai mare decât 7, deci niciun element din subșir nu trebuie deplasat la dreapta. Așadar, acest apel către insert are timp de execuție constant. Să presupunem că fiecare apel al funcției insert are timp de execuție constant. Deoarece se fac $n-1$‍ apeluri către insert, dacă fiecare apel are timpul de execuție $c$‍, atunci timpul total de execuție pentru sortarea prin inserție este $c\cdot (n-1)$‍, adică $\mathrm{\Theta }(n)$‍, nu $\mathrm{\Theta }(n^2)$‍.

Poate avea loc vreuna dintre aceste situații? Se poate ca la fiecare apel către insert să se deplaseze toate elementele din subșir cu o poziție la dreapta? Se poate ca la fiecare apel către insert să nu se deplaseze niciun element? Răspunsul este da la ambele întrebări. Un apel către insert face ca fiecare element să fie deplasat dacă valoarea cheii ce urmează să fie inserată este mai mică decât toate elementele din stânga sa. Așadar, dacă fiecare element este mai mic decât toate elementele din stânga sa, timpul de execuție al sortării prin inserție este $\mathrm{\Theta }(n^2)$‍. Ce ar însemna ca fiecare element să fie mai mic decât elementul din stânga sa? Vectorul ar fi ordonat descrescător, ca în exemplul [11, 7, 5, 3, 2]. Așadar, cazul cel mai nefavorabil pentru sortarea prin inserție este un vector ordonat descrescător.

Ce se întâmplă în cazul opus? Un apel către insert nu deplasează niciun element dacă valoarea cheii ce urmează să fie inserată este mai mare decât sau egală cu toate elementele din stânga sa. Așadar, dacă fiecare element este mai mare decât sau egal cu toate elementele din stânga sa, timpul de execuție al sortării prin inserție este $\mathrm{\Theta }(n)$‍. Această situație se petrece atunci când vectorul este deja sortat, deci un vector ordonat crescător este cazul cel mai favorabil pentru sortarea prin inserție.

Ce altceva putem spune despre timpul de execuție al sortării prin inserție? Să presupunem că elementele din vector sunt în ordine aleatorie. Așadar, în medie, ne-am aștepta ca fiecare element să fie mai mic decât jumătate din elementele din stânga sa. În acest caz, un apel către insert pentru un subșir de $k$‍ elemente ar deplasa $k/2$‍ elemente. Timpul de execuție ar fi jumătate din timpul de execuție al cazului cel mai nefavorabil. Însă, folosind notația asimptotică, unde coeficienții constanți nu sunt luați în considerare, timpul de execuție în cazul mediu ar rămâne în continuare $\mathrm{\Theta }(n^2)$‍, la fel ca în cazul cel mai nefavorabil.

Dar dacă ai fi știut că vectorul este „aproape sortat”: fiecare element se află la cel mult un număr constant de poziții, de exemplu 17, față de poziția pe care ar fi avut-o în vectorul sortat? Atunci fiecare apel către insert deplasează cel mult 17 elemente, iar timpul de execuție pentru un apel către insert pe un subșir de $k$‍ elemente ar fi cel mult $17\cdot c$‍. Luând în calcul toate cele $n-1$‍ apeluri către insert, timpul de execuție ar fi $17\cdot c\cdot (n-1)$‍, care este egal cu $\mathrm{\Theta }(n)$‍, la fel ca în cazul cel mai favorabil. Așadar, sortarea prin inserție este rapidă atunci când vectorul este aproape sortat.

Haide să recapitulăm timpii de execuție ai sortării prin inserție:

Dacă ar trebui să găsești timpul de execuție al sortării prin inserție care se aplică în toate cazurile, răspunsul ar fi $O(n^2)$‍. Nu poți spune că este $\mathrm{\Theta }(n^2)$‍, deoarece în cazul cel mai favorabil este $\mathrm{\Theta }(n)$‍. Nu poți spune nici că este $\mathrm{\Theta }(n)$‍, deoarece în cazul cel mai nefavorabil este $\mathrm{\Theta }(n^2)$‍.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.