Sortarea prin inserție

Există diverse metode de sortare. Pe parcursul execuției sortării prin selecție, elementele ordonate se află în subșirul de la începutul vectorului, iar cele neordonate se află în subșirul de la final. Sortarea prin selecție caută în subșirul nesortat următorul element pe care să îl adauge în subșirul sortat.

Iată un alt mod în care te poți gândi la sortare. Imaginează-ți că participi la un joc de cărți și ții cărțile în mână în ordine crescătoare. Primești o carte nouă pe care trebuie să o așezi la locul potrivit în așa fel încât cărțile tale să fie sortate în continuare. La sortarea prin selecție, fiecare element nou pe care îl adaugi în subșirul sortat are o valoare mai mare decât cele exsitente deja în subșir. Dar, în exemplul nostru, noua carte poate fi mai mică decât unele dintre cărțile pe care le ții deja, așa că trebuie să parcurgi din nou cărțile, comparând noua carte cu fiecare carte din mână, până găsești o poziție pe care să o așezi. Inserezi noua carte la locul potrivit și obții din nou o mână ordonată de cărți. Apoi primești o altă carte și repeți procesul. Apoi o altă carte, încă una, și așa mai departe, până când nu mai sunt cărți de primit.

Aceasta este ideea din spatele sortării prin inserție. Parcurgi în mod repetat indicii din vector, începând de la poziția 1. Fiecare nou indice este echivalentul noii cărți primite și trebuie să îl inserezi pe poziția corectă în subșirul sortat, aflat la stânga indicelui respectiv. Mai jos poți vedea cum funcționează algoritmul:

Într-un exemplu cu vectori, imaginează-ți că subșirul cu indici de la 0 până la $5$‍ este deja sortat, iar noi ne dorim să inserăm elementul de pe poziția 6 în subșirul sortat, în așa fel încât subșirul cu indici de la 0 la 6 să fie sortat. Iată cum începem:

Și iată cum ar trebui să arate subșirul când terminăm:

Pentru a insera elementul de pe poziția 6 în subșirul din stânga sa, îl comparăm în mod repetat cu valorile aflate în acest subșir, de la dreapta la stânga. Haide să denumim elementul de pe poziția 6 - cheie (key). De fiecare dată când găsim un element mai mare decât cheia în stânga sa, deplasăm elementul respectiv cu o poziție la dreapta, deoarece știm că această cheie va trebui să se regăsească în stânga acelui element. Vom avea nevoie de două lucruri pentru această operațiune: o operație permutare care deplasează un element cu o poziție la dreapta și o variabilă în care să salvăm valoarea cheii (pentru a nu fi suprascrisă de elementul din stânga sa). În exemplul nostru, să salvăm elementul de pe poziția 6 în variabila key:

Acum comparăm key cu elementul de pe poziția 5. Observăm că key (5) este mai mic decât elementul de pe poziția 5 (13), așadar îl deplasăm pe 13 pe poziția 6:

Iată că operația de permutare pur și simplu copiază elementul de pe o poziție pe următoarea poziție la dreapta sa. Următorul pas este să comparăm key cu elementul de pe poziția 4. Observăm că key (5) este mai mic decât elementul de pe poziția 4 (10), așadar îl deplasăm pe 10 la dreapta:

În continuare, comparăm key cu elementul de pe poziția 3 și îl deplasăm pe acesta din urmă la dreapta:

Același lucru se întâmplă cu elementul de pe poziția 2:

Ajungem la elementul de pe poziția 1, care are valoarea 3. Acesta este mai mic decât key, deci nu îl deplasăm. În schimb, plasăm key pe poziția din dreapta acestui element (adică pe poziția 2), al cărui element fusese deplasat în prealabil în dreapta. Drept rezultat, subșirul cu indici de la 0 la 6 este acum sortat:

Sortarea prin inserție inserează în mod repetat un element în subșirul sortat din stânga sa. Inițial, putem spune că subșirul ce conține doar indicele 0 este sortat, din moment ce are un singur element, și cum ar putea un singur element să nu fie sortat în raport cu el însuși? Haide să vedem un exemplu. Iată vectorul nostru inițial:

Deoarece subșirul ce conține doar indicele 0 este subșirul nostru inițial sortat, prima cheie este pe poziția 1. (Vom colora subșirul sortat cu roșu, cheia cu galben și subșirul din vector pe care încă nu l-am parcurs cu albastru.) Inserăm cheia în subșirul sortat din stânga sa:

Acum subșirul sortat este de la 0 la 1, iar noua cheie se află pe poziția 2. O inserăm în subșirul din stânga sa:

Continuăm procesul, privind pe rând fiecare element din vector ca fiind cheia și inserându-l în subșirul sortat aflat la stânga sa:

Odată ce am inserat și ultimul element din vector, obținem vectorul sortat:

Două cazuri cu care ne-am întâlnit în exemplul nostru trebuie analizate mai bine: când cheia pe care o inserăm este mai mică decât toate elementele din stânga sa (cum au fost cheile 2 și 3) și când este mai mare sau egală cu toate elementele din stânga sa (cum a fost cheia 13). În primul caz, fiecare element din subșirul din stânga cheii se deplasează cu o poziție la dreapta și trebuie să ne oprim când ajungem în capătul stâng al vectorului. În al doilea caz, prima dată când comparăm cheia cu un element din stânga sa, observăm că aceasta se află deja pe poziția corectă relativ la toate elementele din stânga; niciun element nu trebuie deplasat, iar cheia rămâne pe poziția pe care se afla inițial.

Primul pas la sortarea prin inserție este să eliberăm o poziție din vector pe care să inserăm valoarea curentă, salvată în key. După cum am văzut mai sus, parcurgem subșirul din stânga poziției inițiale a lui key, de la dreapta la stânga, deplasând fiecare element care este mai mare decât key cu o poziție la dreapta. Odată ce găsim un element care este mai mic decât key, sau egal cu key, oprim permutarea și copiem key pe poziția liberă, chiar în dreapta elementului respectiv. Diagrama următoare explică această idee:

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.