Algoritmul de insertion sort

Insertion sort - algortim de sortare(partea I)

     Algoritmul de insertion sort este, probabil, unul dintre cei mai cunoscuti algortimi de sortare intrucat este usor de invatat, iar stapanirea acestuia este un criteriu obligatoriu ce trebuie indeplinit de oricine vrea sa inteleaga algortimi mai complexi derivati din acesta - precum shell sort despre care vom discuta intr-un alt articol.

   Mi-am propus sa va descriu modul de functionare al algortimului, apoi va voi arata implementatia acestuia in 3 limbaje de programare urmand sa va descriu codul de pe fiecare linie.

Descrierea Algoritmului

   Algoritmul presupune formarea unei liste sortate, apoi compararea fiecarui element din lista principala - adica cea nesortata - cu fiecare element din lista nesortata. In functie de aceste comparatii vom decide unde sa inseram elementul curent astfel incat lista sortata sa ramana in continuare sortata. Algoritmul s-ar putea sa va fie destul de familiar, intrucat este modul natural al oamenilor de a sorta lucrurile. Ganditi-va ca vreti sa plasati o carte intr-un pachet de carti astfel incat acesta sa fie in ordine. Cum procedati? Ei bine, comparati cartea in cauza cu fiecare dintre cele aflate deja in pacahet si o introduceti in locul unde apartine in functie de rezultatul acestor coparatii.

    Sa exemplificam modul de functionare. Considerati lista neordonata de numere:

2, 1, 3, 4

    Vom considera ca lista sortata contine doar elementul 2. Deci, vom incepe sa luam fiecare element incepand cu elementul 1 si le vom compara cu fiecare element din lista sortata adaugandu-l pe baza acestor comparatii in lista sortata.

Deci, comparam elementul 1 cu fiecare din lista sortata:

 2, 1, 3, 4

Cum, deocamdata, lista sortata este compusa doar din elementul 2, il vom compara pe 1 cu 2. 2 este mai mare ca 1, deci ar trebui sa le schimbam pozitiile intre ei astfel:

                                                                           2, 1, 3, 4

                                                                           1, 2, 3, 4

Dupa cum vedeti, elemente 1 si doi si-au schimbat pozitiile intre ele. acum lista noastra ordonata contine elementele: 1, 2. Trecem la urmatorul element, 3, si-l vom compara cu fiecare element din lista ordonata:

                                                                           1, 2, 3, 4

Doi este mai mare ca 3? Nu. Deci, nu mai are sens sa-l comparam pe 3 si cu celelalte elemente din lista ordonata intrucat daca 2 - numarul cel mai mare la acest momenet din lista ordonata - nu este mai mare ca 3, atunci nici 1 nu va fi mai mare ca 3. Asa ca 3 isi pastreaza pozitia. Lista ordonata arata astfel: 1, 2, 3. Trecem la urmatorul element.

                                                                          1, 2, 3, 4

Il vom compara pe 4, pe rand, cu fiecare element din lista ordonata. 3 este mai mare ca 4? Nu. Deci nu mai are sens sa-l comparam si cu celelalte. 4 isi pastreaza pozitia.

Dupa cum puteti vedeam am sortata lista.

Sa luam un alt exemplu:

3, 4, 2, 1

Lista sortata contine elementul 3. Vom compara fiecare element din lista nesortata cu fiecare din lista sortata. 

3, 4, 2, 1

Ia sa vedem. 3 este mai mare decat 4? Nu. Deci, 4 isi pastreaza pozitia. Lista sortata arata acum astfel: 3, 4. Trecem, la urmatorul element:

                                                                          3, 4, 2, 1

Il vom compara pe doi cu fiecare element din lista sortata. 4 este mai mare decat 2? Da. Deci 4 ar trebui sa treaca pe pozitia lui 2 iar doi pe pozitia lui patru:

                                                                         3, 4, 2, 1

                                                                         3, 2, 4, 1

Dupa cum spuneam, il comparam pe doi cu fiecare element din lista sortata, dar a mai ramas 3. Deci, 3 este mai mare ca doi? Categoric da. Deci, 3 ar trebui sa treaca pe pozitia lui 2 si 2 pe pozitia lui 3.

                                                                         3, 2, 4, 1

                                                                        2, 3,  4, 1

L-am comparat pe doi cu fiecare element din lista sortata pana am putut stabili cu exactitate pozitia lui in lista.  Lista noastra sortata ara asa acum: 2, 3, 4. Acum puteam trece la urmatorul element, 1.

                                                                         2, 3, 4, 1

Il vom compara pe 1 cu fiecare element din lista sortata. 4 este mai mare ca 1? Da! deci 4 si 1 ar trebui sa schimbe pozitiile intre ei.

                                                                         2, 3, 4, 1

                                                                         2, 3, 1, 4

Il comparam pe 1 cu urmatorul element din lista sortata. 3 este mai mare ca 1? Da, da, da. deci 3 si 1 ar trebui sa schimbe pozitiile intre ei.

                                                                         2, 3, 1, 4

                                                                         2, 1, 3, 4

Il comparam pe 1 cu ultimul element din lista sortata pentru a vedea daca ii mai schimbam pozitia sau daca va rama acolo unde este. 2 este mai mare decat 1? Da. deci 2 si 1 ar trebui sa schimbe pozitiile intre ei.

                                                                        2, 1, 3, 4

                                                                        1, 2, 3, 4

Intr-un final, avem o lista sortata(crescator).

Probabail ca ati remarcat ca aceasta "lista ordonata/sortata" de care tot aduc vorba face parte din lista principala pe care vrem sa o sortam. Este doar un concept abstract folosit pentru a explica mult mai bine modul de functionare al algoritmului.

Implementatia algortimului

   Nu ne mai ramane decat sa implementam acest algortim intr-un limbaj de programare. Din motive obiective il voi implemeneta in 3 limbaje: C, Python si PHP.

Sa incepem cu implementatia in C:

for(i = 0; i < n; i++) {
        currentElement = v[i];
        for(j = i - 1; j >= 0; j--) {
            if(currentElement < v[j]) {
                v[j + 1] = v[j];
                v[j] = currentElement;
            }
            else {
                break;
            }
        }
    }

Pe linia 1 aveam o bucla for ce va duce variabila de ciclare i de la valoarea 1 la n-1. De ce incepem de la 1? Pentru ca primul element al array-ului va reprezenta lista sortata. Aminteste-ti ca array-urile sunt indexate de la 0. 

Pe linia 2 salvam valoarea aflata in elementul v[i], deci elementul de indice i in variabila currentEelement. 

Pe linia 3 avem o bucla for in care initializam variabila de ciclare j cu valoarea i-1. Cine este elementul de indice i-1? Exact elementul din spatele celui curent, deci primul element din lista sortata - daca ar fi sa numaram de la stanga la dreapta. Punem conditia ca bucla sa ruleze pana cand j ia(inclusiv) valoarea 0. La fiecare etapa a buclei decrementam variabila j cu o unitate.

Pe linia 4 verificam daca elementul de indice j este mai mare decat elementul curent. Cine este acest element de indice j? Exact, elementul din spatele lui currentEelement. In cazul in care elementul de indice j este mai mare decat currentElement trecem pe ramura de adevar(TRUE) a if-ului.

Pe linia 5 "spunem" ca pozitia j+1 din array va fi ocupata de elementul de pe pozitia j.  Atentie! Cine este elementul de pe pozitia j+1 ? Elementul curent. Deoarece am salvat valoarea elementului curent in variabila currentElement aceasta nu este pierduta.

Pe linia 6 ocupam pozitia j a array-ului cu valoarea salvata in variabila currentElement. Practic, pe aceste doua linii de cod, 5 si 6, am interschimbat pozitia elementului curent cu cea a elementului din lista ordonata ce este mai mare ca acesta. Acest procedeu se va repeta pana cand nu va mai fi niciun element in lista ordonata mai mare decat cel curent.

Pe linia 7 oprim cea de a doua bucla. Intrucat am patruns pe ramura else a if-ului, deci nu mai sunt elemente mai mari decat cel curent in lista ordonata.

Desigur, am fi putut sa evitam utilizarea constructului break prin alterarea conditiei din cea de a doua bucla. Dar am considerat ca ar fi mult mai usor de inteles asa.