Sortarea prin inserție

Sortarea prin inserție este felul în care majoritatea oamenilor își aranjează cărțile din mână: se ia următoarea carte și se strecoară la locul potrivit printre cărțile deja în ordine. Este lentă pe liste lungi aleatorii, dar foarte rapidă pe liste scurte sau aproape sortate, motiv pentru care bibliotecile de sortare reale încă o folosesc.

Bare în curs de sortare, cu o parte sortată în stânga și o bară care alunecă înapoi în ea, peste barele mai mari
Bare în curs de sortare, cu o parte sortată în stânga și o bară care alunecă înapoi în ea, peste barele mai mari

Ideea

Păstrați începutul listei sortat. La început, partea sortată este doar prima valoare. Luați următoarea valoare și comparați-o cu valoarea dinaintea ei. Dacă aceea e mai mare, interschimbați-le și comparați din nou, cu o poziție mai în spate. Opriți-vă când valoarea dinainte nu e mai mare sau când valoarea ajunge la început. Partea sortată a crescut cu o valoare. Repetați cu fiecare valoare până la sfârșit.

Un exemplu

Luați 5, 1, 4, 2, 8. Trecerea 1 ia 1: 5 e mai mare, deci se interschimbă, iar 1 ajunge la început: 1, 5, 4, 2, 8. Trecerea 2 ia 4: se interschimbă cu 5, apoi se oprește la 1: 1, 4, 5, 2, 8. Trecerea 3 ia 2: se interschimbă cu 5 și cu 4, apoi se oprește la 1: 1, 2, 4, 5, 8. Trecerea 4 ia 8, care e deja mai mare decât 5, deci ajunge o comparație. În total, 7 comparații și 4 interschimbări. Metoda bulelor are nevoie de 9 comparații pe aceeași listă, sortarea prin selecție de 10.

Interschimbările sunt egale cu inversiunile

O inversiune este o pereche de valori în ordine greșită. Interschimbarea a doi vecini aflați în ordine greșită elimină exact o inversiune, iar sortarea prin inserție interschimbă doar astfel de vecini. Așadar face exact atâtea interschimbări câte inversiuni are lista inițială, la fel ca metoda bulelor. Fiecare trecere face și cel mult o comparație care nu duce la o interschimbare: cea care o oprește. Deci comparațiile sunt inversiunile plus cel mult n − 1.

Adaptivă: rapidă când lista e aproape sortată

Pentru că munca înseamnă numărul de inversiuni plus aproximativ n, sortarea prin inserție e rapidă ori de câte ori există puține inversiuni. O listă sortată necesită n − 1 comparații și nicio interschimbare. O listă în care fiecare valoare e la doar câteva poziții de locul ei durează un timp apropiat de n. Doar o listă departe de a fi sortată, cum e una inversată, cu n(n − 1)/2 inversiuni, durează un timp proporțional cu n². Pe o listă aleatorie, media este de aproximativ n²/4 interschimbări.

Unde se folosește

Sortarea prin inserție este stabilă, nu are nevoie de memorie suplimentară și are un cost suplimentar foarte mic. Pe liste scurte învinge algoritmi care sunt mai rapizi pe hârtie. Multe sortări din biblioteci, cum sunt Timsort din Python și Java și introsort din C++, trec la sortarea prin inserție pentru bucățile mici ale listei, de obicei de până la câteva zeci de valori. Se potrivește și datelor care sosesc câte o valoare, pentru că fiecare valoare nouă poate fi inserată imediat ce apare.

Explorați

Deschideți aplicația și apăsați Redare sau apăsați Pas ca să avansați câte o comparație. Valoarea inserată are propria culoare, valoarea cu care e comparată e evidențiată, iar partea sortată e verde. Spre deosebire de metoda bulelor și de sortarea prin selecție, partea verde nu e definitivă: o valoare ulterioară, mai mică, poate încă să alunece în ea. Încercați o listă aproape sortată ca să vedeți cât de scurte sunt trecerile, apoi una inversată.

Întrebări frecvente

Care este complexitatea în timp a sortării prin inserție?

O(n²) în cel mai rău caz și în cazul mediu și O(n) în cel mai bun caz, o listă deja sortată. Mai precis, timpul este proporțional cu n plus numărul de inversiuni. Are nevoie doar de O(1) memorie suplimentară.

Care este diferența dintre sortarea prin inserție și sortarea prin selecție?

Sortarea prin selecție parcurge toată partea nesortată ca să găsească cea mai mică valoare, așa că face mereu n(n − 1)/2 comparații, dar puține interschimbări. Sortarea prin inserție ia următoarea valoare așa cum vine și o mută înapoi doar cât e nevoie, așa că face mai puține comparații, mai ales pe liste aproape sortate, dar mai multe interschimbări.

Ce este sortarea prin inserție binară?

O variantă care găsește locul noii valori printr-o căutare binară în partea sortată, ceea ce necesită aproximativ log n comparații în loc de până la n. Valorile tot trebuie mutate ca să se facă loc, așa că numărul de mutări și cel mai rău caz, O(n²), rămân aceleași.

Este sortarea prin inserție stabilă?

Da. O valoare se mută înapoi doar peste valori strict mai mari, așa că valorile egale își păstrează ordinea inițială.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați sortarea prin inserție