Insertion sort - algortim de sortare(partea II)

     Am revenit si cu partea a doua din micul nostru tutorial despre algortimul de insertion sort. In aceasta partea va voi prezenta si descrie implementatia algortimului in alte doua limbaje de programare, Python si PHP. Pe finalul acestei parti va propun sa ne detasam de modul clasic de invatare si sa abordam problema mai neconventional.

Implementatia in Python 

for i in range(1, n): 
    value = v[i]
    j = i - 1
    while j >= 0
        if value < v[j]: 
            v[j + 1] = v[j] 
            v[j] = value
            j = j - 1 
        else :
            break

Modul de functionare este aproape identic cu cel al programului scris in C, deci vom explica doar particularitatile limbajului Python in detaliu.

Pe linia 1 avem o bucla for ce spune ca variabila i va lua valori de la 1 pana la n. n reprezinta numarul de elemente ale listei. Atentie! i nu va lua valoarea n, valoarea maxima pe care o va lua i este n-1. Aminteste-ti, din nou, ca listele sunt indexate de la 0.

Pe linia 2 initializam variabila value cu valoarea elementului de indice i din lista v.

Pe linia 3 initializam variabila j cu valoarea i - 1. Iti este familiara aceasta secventa? Acelasi lucru l-am facut si in pareta anterioara a tutorialului, doar ca atunci am initializat acea variabila prin for.

Pe linia 4 aveam o bucla while ce va rula pana cand variabila de ciclare j va lua valoarea 0.

Pe linia 5  avem o operatie decizionala dictata de conditia ca elementul de indice j sa fie mai mare ca variabila value in care avem stocata valoarea elementului curent.

Pe liniile 6 si 7 inversam pozitiile celor doua elemente din lista, respectiv value cu v[j]. Atentie! Dupa cum am mentionat si in partea I, v[j] este elementul din stanga celui curent, deci v[j] apartine liste sortate.

Pe linia 8 decrementam variabila j, deci scadem 1 din valoarea ei.

Pe linia 10  oprim bucla intrucat am patruns pe ramura else a operatiei conditionale, deci nu mai exista elemente mai mari ca value in lista sortata. Prin urmare, value a ajuns la pozitia destinata.

Implementatia in PHP

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

Dupa cum, probabil, ati oservat, implementatia in PHP a algortimului este mai mult decat identica cu cea in C - exceptand cateva mici particularitati ale PHP-ului. Consider ca nu mai este necesara descrierea detaliata a codului.

Desigur, am fi putut itera array-ul folosindu-ne de un foreach, dar aceasta miscare s-ar fi sondat cu linii de cod in plus astfel incat sa puteam modifica elemente din array-ul pe care il iteram prin intermediul foreach-ului. Ia aminte ca modificarea elementelor unui array in interiorul buclei foreach poate duce la comportament impredictibil.

Problema: 
Cum am putea evita folosirea constructului break?

Raspuns:
Vom modifica conditia astfel:

for($i = 1; $i < $n; $i++) {
    $value = $array[$i];
    for($j = $i - 1; $j >= 0 && $value < $array[$j]; $j--) {
        $array[$j + 1] = $array[$j];
        $array[$j] = $value;
    }
}

Mult mai elegant, nu-i asa? Practic am renuntat la operatia decizionala, iar cea de a doua bucla exista doar pentru a-l interschimba pe $value cu valorile mai mari decat el din array-ul sortat. Cand nu mai sunt valori mai mari decat $value in array-ul sortat bucla se opreste.

Deci, cum s-ar citi noua conditie? Simplu, atat timp cat $j este mai mare sau egal cu 0 si exista valori mai mari decat $value in partea sortata a array-ului.

Observa ca mi-am adaptat terminologia in functie de limbaj.

Problema 2:
Modifica codul astfel incat sa sorteze un array in ordine descrescatoare.

Raspuns:
Pentru a obtine acest rezultat trebuie sa inlocuim doar un operator, respectiv operatorul <,

$value < $array[$j]

deci vom aveam:

$value > $array[$j]

Conditia noastra se va citi acum astfel: atat timp cat j este mai mare sau egal ca 0 si exista elemente mai mici decat $value. Astfel, $value va interschimba pozitiile cu elementele mai mici decat el din lista sortata(descrescator). Practic, $value va fi mutat spre stanga pana cand nu vor mai fi valori mai mici decat el in array-ul sortat.

O alta modalitate de abordare

   Ce spuneti de acest clip? Vi se pare familiar acest dans?

De asemenea, daca doriti mai mult material de studiu va recomand urmatoarele: