Quick Sort

Quicksort

(algortim)

    Quicksort este un algortim de sortare inventat de Tony Hoare in 1960 si este unul ditre cei mai utilizati algortimi de sortare, in practica.

Practic, algoritmul presupune alegera unui element din lista pe care vrem sa o sortam si sa plasam elementele mai mici ca acel element(i se mai sune si pivot) in stanga lui, iar pe cele mai mari in dreapta lui. Dupa acest pas, pivotul, adica elementul ales mai devreme, se afla pe pozitia lui finala - adica in lista sortata pivotul se va gasi tot pe aceasta pozitie.

Sa luam un exemplu:

9, 4, 5, 3, 1, 10

Pentru acest tutorial ne vom limita la varianta de quicksort ce foloseste pivot ales din mijlocul listei. Pivotul nostru este 5. Acum vom plasa elementle mai mici decat pivotul, adica 5, in stanga lui, iar elementele mai mari ca acesta in drapta lui.

1, 4, 3, 5, 10, 9

Dupa cum vedeti, pivotul a ajuns in pozitia lui finala. Atunci cand lista va fi sortata pivotul, adica 5, va ramane tot pe poztia in care se afla acum.

    Acest pas de "triere" a elementelor unei liste in functie de un pivot se numeste partitionare. In acest pas singurul lucru care ne intereseaza este sa plasm elementele mai mici dacat pivotul in stanga lui iar pe cele mai mari ca el in dreapta lui. Nu ne intereseaza daca elemntele ce au fost plasate in dreapta sau stanga pivotului se afla in ordine. 

Probabil te intrebi de ce am pus in stanga lui 5 elementele 1, 4, 3 si de ce nu 1, 3, 4? Tot ce am vrut prin acel exemplu era sa-ti arat ca la partitionarea  listei singurul lucru care conteaza este sa plasam elementle mai mari ca pivotul in dreapta si cele mai mici ca el in stanga, nu are nicio importanta daca acestea se afla in ordine sau nu.

    Dupa ce am partitionat lista se poate observa ca avem acum doua subliste: cea formata din elementele din stanaga pivotului si cea formata din elementele din dreapta pivotului. Tot ce avem acum de facut este sa partitionam acum fiecare sublista in parte, iar, dupa acest pas, sa partitionam subsubliste ce sau format din sublistele formate din lista initiala. 

Acest proces recursiv de partitionare a sublistelor formate din lista initiala se numeste reprezinta quicksort. Ca orice alt algoritm recursiv, quicksort, cazul de baza a lui quicksort este atunci cand lista contine 1 sau 0 elemente. In acest caz nu se mai face partitionarea, pentru ca nu se poate sa ai dezordine intr-o lista cu doar un sigur element.

     Rezumand ce am spus mai sus reiese urmatoarea schita:

          1) partitionarea listei

          2) partitionarea recursiva a sublistelor formate pana la atingerea cazului de baza

Grep

Program care printeaza liniile ce contin un anumit tipar

   Cei care folosesc linux au auzit, poate, de programul grep. Astazi o sa incercam sa implementam o versiune mai minimalista a acestuia in limbajul de programare C.

Rationamentul necesar pentru a crea un astfel de program este destul de simplu. In primul rand, ce dorim sa facem? Dorim sa facem un program care printeaza fiecare linie introdusa de utilizator ce contine un anumit tipar specificat de noi in "interiorul programului".
Sa spunem ca tiparul este test, daca utilizatorul introduce linia "am scris test", atunci, programul nostru o va printa din nou. Daca introduce input ce nu contine nici o ocurenta a acelui tipar, atunci nu o mai printam.

Rezumand ce am spus mai sus, asta ar fi schita programului:

cat timp utilizatorul introduce o linie executa
    daca linia contine o ocurenta a tiparului atunci
        printeaza acea linie

Iata si codul sursa:

#include < stdio.h >
#define MAXLINE 1000

int getline(char s[], int lim);
int strindex(char s[], char t[]);

int main() {
    char pattern[] = "test";
    char s[MAXLINE];

    while(getline(s, MAXLINE)) {
        if(strindex(s, pattern) >= 0) {
            printf("%s", s);
        }
    }
    return 0;
}

int getline(char s[], int lim) {
    int c, i;

    i = 0;
    while(--lim > 0 && (c = getchar()) != EOF && c != '\n') {
        s[i++] = c;
    }

    if(c == '\n') {
        s[i++] = c;
    }
    s[i] = '\0';

    return i;
}

int strindex(char s[], char t[]) {
    int i, j, k;

    for(i = 0; s[i] != '\0'; i++) {
        for(j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++)
            ;

        if(k > 0 && t[k] == '\0') {
            return i;
        }
    }
    return -1;
}

Programul nostru foloseste 3 functii esentiale - nemaipunand-o la socoteala pe main(). Aceste functii sunt: getline - folosita pentru a prelua input de la utilizator, strindex - folosita pentru a verifica ocurenta tiparului in string si printf - pentru a printa linia ce contine cel putin o ocurenta a tiparului. Din fericire functia printf a fost deja scrisa pentru noi de catre alti programatori, asa ca noi mai avem de implementata doar doua functii, respectiv getline si strindex.
Codul de mai sus a fost extras din cartea "The C programming language".

   Haideti sa explicam mecanismul de functionare al codului nostru. Sa incepem cu implementatia functiei getline. Declaram doua variabile de tipul int, c pentru a retine fiecare caracter, in parte, din linia citita si i pentru a tine evidenta  elementelor din array-ul unde se vor stoca caracterele citite.
Initializam variabila i cu valoarea 0 pentru a stoca elemente in array-ul s incepand de la indexul 0. Pe urmatoarea linie avem o bucla while ce se va opri atunci cand am depasit limita de caractere impusa pe o linie. Totusi, observi ca mai intai decrementam variabila lim si apoi o comparam cu valoarea 0. Probabil, te intrebi de ce? Facem acest lucru pentru a pastra o pozitie din array libera pentru caracterul null. Astfel, array-ul nostru va contine maxim 999 de caractere diferite de cel null  si caracterul null. Atunci ca observi operatorul de decrementare(--) sau de incrementare(++) in fata unei variabile, spunem ca am predecrementat/preincrementat acea variabila. Deci, lim va lua valoarea lim-1 si apoi va fi evaluata.

Urmatoarea conditie de oprire a buclei este ca sa ajungem la sfarsitul fisierului, daca am ajuns la sfarsitul fisierului oprim bucla. Cand am ajuns la sfarsitul fisierului variabila c va lua valoarea EOF - din acest motiv am declarat variabila c ca fiind int, pentru a putea retine valoarea sfarsitului de fisier.

Ultima conditie de oprirere a buclei este ca c sa ia valoarea line feed-ului('\n'). Totusi, te vei intreba de ce oprim bucla atunci cand gasim un line feed, dar pe liniile imediat urmatoare verificam daca c este egal cu un line feed, si daca este adaugam acel line feed in s. Vei spune ca am putea scoate ultima conditie din while si if-ul imediat urmator. Daca am face asa cum spui tu atunci functia noastra ar citi pana cand ajunge la sfarsitul fisierului, nu pana ala sfarsitul liniei. Deci array-ul s ar putea contine mai multe line feed-uri.

Dupa ce am adaugat line feed-ul in s, adaugam caracterul null pe pozitia imediat urmatoare si returnam valoarea varibilei i care este egala cu lungimea stringului s.

Sa descriem modul de functionare a functiei strindex.
Declaram 3 variabile de tipul int, i, j si k.  Pe linia urmatoare avem o bucla for ce duce variabila i pana cand s[i] va fi egal cu caracterul null, deci pana cand caracterul null se va afla pe pozitia i in array-ul s. 
In interiorul buclei for mai avem o alta bucla for ce initializeaza variabila j cu valoarea lui i si variabila k cu valoarea 0. Astfel, bucla va rula atat timp cat caracterul de pe pozitia j din s va fi egal cu caracterul de pe pozitia k din t si cat timp t[k] va fi diferit de caracterul null - deci, pana ajungem la sfarsitul stringului.

Apoi, in if-ul de pe pozitia urmatoare verificam daca bucla a rulat cel putin o data(k > 0) si daca a rulat pana la sfarsitul stringului(t[k] == '\0'). Prima conditie poate fi indeplinita daca unul sau mai multe caractere din s au fost egale cu cele din t, dar, atat timp cat nu au fost toate egale, inseamna ca nu se gaseste tiparul t in s. Daca conditia impusa de if a fost indeplinita cu succes, atunci returnam valoarea variabilei i - deci valoarea indexului din s de unde incepe prima ocurenta a tiparului t. In caz contrar returnam -1, avand in vedere ce array-urile sunt indexate de la 0, o valoare negativa este destul de convenabila pentru a exprima un status de eroare.

Codul din main() este foarte simplu, bucla while va rula atat timp valoarea returnata de getline este diferita de 0 - aceasta poate fi 0 atunci cand am ajuns la sfarsitul fisierului.
In interiorul buclei verificam daca in linia citita apare tiparul t, daca apare - adica valoarea returnata de strindex este mai mare sau egala cu 0 - printam linia abia citita.
   

Inversul unui cuvant in C

Inversul unui cuvant in C

   In tutorialul de astazi mi-am propus sa va explic cum ar trebui sa abordam aceasta problema, respectiv cea a intoarcerii unui cuvant, in limbajul de programare C.

Pentru inceput, ce reprezinta inversul unui cuvant? Sa luam cuvantul test, inversul lui este tset. Inversul lui craciun este nuicarc. Ei bine, cum vom duce la bun sfarsit aceasta prolema? Stim ca fiecare caracter din cuvantul pe care dorim sa-l intoarcem este stocat intr-un array, astfel puteam accesa fiecare caracter, in parte, si putem face operatii majore aupra cuvantului intreg.
O prima idee ar fi sa copiem caracter cu caracter din primul array, de la sfarsit spre inceut, intr-un alt array.

#include < stdio.h >
#include < string.h > 

int main() {
    char string1[] = "test";
    char string2[5];
    int i, j;
    int n = strlen(string1);

    for(i = 0, j = n - 1; i < n; i++, j--) {
        string2[i] = string1[j];
        //printf("%d  %d\n", i, j);
    }
    string2[i] = '\0';

    printf("%s", string2);

    return 0;
}

In codul de mai sus, parcurgem caracter cu caracter din variabila string1 de la sfarsit spre inceput si il salvam in variabila string2. Astfel, variabila string2 va contine reprezentarea inversului cuvantului pe care am dorit sa-l intoarcem.

In bucla for din codul nostru, atribuim caracterul de pe pozitia j din array-ul string1 elementului string2[i]. La primul ciclu al buclei, cand variabila i are valoarea 0 si variabila j are valoarea 3, 
elementul string2[0] va retine valoarea stocata in variabila string1[3] - deci, ultimul caracter din array-ul string1.

Programul nostru isi duce la bun sfarsit misiunea, dar nu in cel mai eficient mod - folosind si variabila string2 ocupam memorie in plus. Exista un mod mai elegant de indeplini aceasta cerinta. El se bazeaza pe faptul ca putem inversa primul caracter al unui cuvant cu ultimul, al doilea cu penultimul, al treilea cu antepenultimul. Vom continua asa pana cand nu vor mai fi caractere de inversat, atunci constatam ca am inversat cuvantul.

Exemplu:

test

Vom inversa primul caracter, t, cu ultimul caracter - coincidenta face ca acesta sa fie tot t.

test

Acum inversam al doilea caracter cu penultimul. Dupa acest pas observam ca nu mai avem ce inversa, deci ne-am indeplinit cerinta.

tset

Iata si codul:

#include < stdio.h >
#include < string.h >

int main() {
    char string[] = "test";
    char temp;
    int i, j;

    for(i = 0, j = strlen(string) - 1; i < j; i++, j--) {
        temp = string[i];
        string[i] = string[j];
        string[j] = temp;
    }

    printf("%s", string);
    
    return 0;
}

Probabil ati observat si mai sus ca folosim headerul <string.h>, prezenta acestuia in codul nostru se datoreaza folosirii functiei strlen() ce este declarata in acest header, aceasta functie returneaza lungimea stringului ce i-a fost pasat drept argument..
Variabila temp este folosita pentru a putea inversa elementele de pe pozitiile i si j - probabil vom vorbi intr-un tutorial viitor despre acest procedeu.

S-ar putea sa te intrebi de ce am pus drept conditie de oprire a buclei i < j. Pentru a raspunde la aceasta intrebare trebue a abordam problema mai abstract. Inversam caracterele aflate la o anumita distanta pana cand ajungem la mijloc, daca numarul de caractere al cuvantului este par, atunci, avem 2 mijlocuri. Dupa ce am facut inversia caracterelor din mijloc trebuie sa ne oprim pentru ca am inversat cuvantul. In cazul in care numarul de caractere ale cuvantului este impar, atunci, avem un singur mijloc. In acest caz vom inversa caracterele din cuvant pana ajungem la mijloc. Ultimele caractere inversate vor fi cele din jurul mijlocului.

Practic, asta ar trebui sa vizualizati cand inversam un cuvant cu numar par de caractere. Incercati, pur si simplu, sa invartiti cuvantul in mintea voastra.

Asta ar trebui sa vizualizati cand doriti sa inversati un cuvant cu numar impar de caractere.

Deci, daca vom continua sa inversam caractere pana cand i va fi mai mare ca j, nu vom face decat sa readucem cuvantul in forma initiala. Vom inversa inversul cuvantului, de asta ne oprim la mijloc. Daca trecem de acea bariera care este mijlocul, atunci, inversam caracterele care au fost deja inversate, deci readucem cuvantul la forma initiala. - iar noi nu vrem acest lucru.

In cazul cuvantului cu numar impar de caractere craciun, puteti observa ca vom inversa caractere pana cand ajungem la caracterul c - caracterul din mijloc, respectiv limita. Indecsi i si j nu pot trece acea limita.

Puteti observa in cazul cuvantului cu numar par de caractere test limitele pe care trebuie sa le atinga fiecare index. Daca am incalca aceasta limita, i ar deveni mai mare ca j, iar daca noi vom inversa caracterul de pe pozitia i cu cel de pe pozitia j, nu vom face decat sa aducem caracterele in forma initiala.

Shel sort - algortim de sortare

Shel sort - algortim de sortare

   Astazi mi-am propus sa vorbim despre un algoritm de sortare ceva mai special fata de cel precedent, insertion sort. Algoritmul a fost descoperit in 1959 de D. L. Shell - de aici provine si denumirea de "Shell sort". Practic, algoritmul este o generalizare a insertion sort.

Descrierea algoritmului

   In etapele de inceput se sorteaza subsiruri din cel principal, aceste subsiruri au elementele la o distanta prestabilita. In etapele de inceput numarul acestor subsiruri este mare, dar acestea contin putine elemente. Pe masura ce avansam, numarul subsirurilor se imputineaza, dar numarul elementelor acestor subsiruri creste. Intr-un final vom ramane doara cu un sir, iar de aici se aplica algortimul de insertion sort clasic.

Sa nu o mai lungim si s atrecem la un exemplu practic:

Sa luam sirul:

6, 5, 4, 3, 2, 1 

   Dupa cum spuneam, se va face sortare pe mai multe subsiruri. Cum stabilim numarul de subsirurilor de inceput? Stabilind distanta dintre elemente la fiecare cilclu. Conform autorului, la inceput acest interval va avea valoarea [n/2], n reprezinta numarul de elemente ale sirului, iar prin [ si ] reprezentam partea intrega a acelui numar. Ai uitat ce reprezinta partea intreaga?

Partea intreaga reprezinta valoarea din partea stanga a virgulei, partea intreaga a numarului 6.5 este 6, partea intreaga a numarului 8.999999 este 8.

Pe masura ce inaintam spre un alt ciclu injumatatim aceasta valoare, adica la al doilea ciclu al buclei valoarea acestui interval va fi [[n/2]/2],  adica am injumatatit valoarea intervalului de la ciclul precedent si i-am luat partea intreaga. 

   Sirul nostru contine 6 elemente, deci distanta dintre elemente va fi de [6/2] = 3. Acestea sunt intervalele: 

6, 5, 4, 3, 2, 1

6, 5, 4, 3, 2, 1

6, 5, 4, 3, 2, 1

Aplicam algortimul clasic de insertion sort pe fiecare dintre aceste 3 siruri, incepem cu primul:

6, 5, 4, 3, 2, 1

Sirul sortat contine elementul 6, il vom compara pe 3 cu fiecare element din sirul sortat pentru a stabili unde il inseram. Deoarece sirul sortat al subsirului format din 6 si 3 contine doar elementul 6 il vom compara pe 3 cu 6. Deoarece 6 este mai mare ca 3, acestea vor schimba pozitiile. Asa arata subsirul 1 acum:

3, 5, 4, 6, 2, 1 

Elementele ce compun subsirul 1, 3 si 6, sunt in ordine. Avansam la urmatorul subsir, cel format din elementele 5 si 2.

3, 5, 4, 6, 2, 1

Aplicam algorimul clasic de insertion sort pe acest subsir. 5 este mai mare ca 2? Da, deci acestea vor interschimba pozitiile. Asa arata subsirul 2 acum:

3, 2, 4, 6, 5, 1

Si cel de al doilea sir este sortat, elementele  ce compun sirul, 2 si 5, sunt in ordine. Trecem la ultimul subsir:

3, 2, 4, 6, 5, 1

4 este mai mare decat 1? Da! Deci elementele 4 si 1 vor interschimba pozitiile. Asa arata subsirul nostru acum:

3, 2, 1, 6, 5, 4

Intr-un final, puteam observa ca am sortat toate cele 3 subsiruri:

3, 2, 1, 6, 5, 4

3, 2, 1, 6, 5, 4

3, 2, 1, 6, 5, 4

Acum ca am sortat toate cele 3 sirui, vom injumatati valoarea intervalului extragand doar partea intreaga din acesta: [[6/2]/2] - dar cine este [6/2]? 3. Deci [3/2] = 1. Daca distanta dintre elemente este 1, atunci avem doar un singur subsir - intrucat distanta dintre elementele acestui subsir este 1. Deci, subsirul nostru este:

3, 2, 1, 6, 5, 4  

Dar subsirul nostru este chiar sirul principal pe care vrem sa-l sortam, de aici aplicam algortimul clasic de insertion sort. Incepem de la elementul de indice 1, deci:

3, 2, 1, 6, 5, 4

Il comparam pe 2 cu fiecare element din lista sortata, care este compusa doar din 3 la a acest moment. Deci, 3 este mai mare ca 2? Da! acestea doua vor interschimba pozitiile. Sirul nostru va arata asa:

2, 3, 1, 6, 5, 4

Trecem la urmatorul element, 1, si-l vom compara cu fiecare elemnt din lista sortata pentru a decide unde-l vom insera. 

2, 3, 1, 6, 5, 4

3 este mai mare ca 1? Da. 3 si 1 vor schimba pozitiile.

2, 1, 3, 6, 5, 4

2 est mai mare ca 1? Da. 2 si 1 vor schimba pozitiile.

1, 2, 3, 6, 5, 4

Pentru a sorta sirul in continuare trebuie doar sa continui sa aplici insertion sort - despre care am vorbit in ultimele 2 tutoriale.

Sa luam sirul format din elementele:

8, 7, 6, 5, 4, 3, 2, 1

Pentru inceput vom aveam [8/2] - deoarece sirul are 8 elemente, n=8 - deci intervalul dintre elementele primelor subsiruri va fi 4. Iata subsirurile:

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

8, 7, 6, 5, 4, 3, 2, 1

Vom aplica algortimul de insertion sort pe fiecare dintre aceste subsiruri. Incepem cu primul:

8, 7, 6, 5, 4, 3, 2, 1

Tot ce avemd e facut este sa aplicam algortimul de insertion sort pe sirul ce contine elementele  8 si 4. 8 va fi primul element al sirului sortat, deci il vom compara pe 4 cu 8 pentru a decide unde-l inseram pe 4. 8 este mai mare ca 4, deci 8 si 4 vor schimba pozitiile.

4, 7, 6, 5, 8, 3, 2, 1

Primul subsir este sortat, trecem la urmatorul.

4, 7, 6, 5, 8, 3, 2, 1

Il vom compara pe 3 cu 7 - elementul ce compune sirul sortat al subsirului format din elementele 7 si 3. 7 este mai mare decat 3, deci aceste vor schimba pozitiile.

4, 3, 6, 5, 8, 7, 2, 1

Cel de al doilea subsir este sortat, trec la al treilea.

4, 3, 6, 5, 8, 7, 2, 1

6 este mai mare ca 2? Da. 2 si 6 vor schimba pozitiile.

4, 3, 2, 5, 8, 7, 6, 1

Si cel de al treilea subsir este sortat, trecem la ultimul.

4, 3, 2, 5, 8, 7, 6, 1

5 este mai mare ca 1? Da! Deci 5 si 1 vor schimba pozitiile.

4, 3, 2, 1, 8, 7, 6, 5

Am sortat toate cele 4 subsiruri, acum putem sa injumatatim valoarea intervalului. Deci, [4/2]=2. Distanta dintre elementele sirurilor ce se vor forma este de 2. Acestea sunt subsirurile:

4, 3, 2, 1, 8, 7, 6, 5

4, 3, 2, 1, 8, 7, 6, 5

Incepem cu primul subsir, cel format din elementele: 4, 2, 8, 6. Sirul sortat este format din elementul 4, vom compara fiecare element din sirul nesortat cu fiecare din sirul sortat pentru a decide unde-l inseram. 

4, 3, 2, 1, 8, 7, 6, 5

Il comparam pe 2 cu 4. 4 este mai mare ca 2, deci aceste elemente vor schimba pozitiile.

2, 3, 4, 1, 8, 7, 6, 5

Trecem la urmatorul element, 8:

2, 3, 4, 1, 8, 7, 6, 5

Nu este niciun element mai mare ca 8 in sirul sortat, deci trecem mai departe la elementul 6.

2, 3, 4, 1, 8, 7, 6, 5

8 este mai mare ca 6? Da. deci 8 si 6 ar trebuis a schimbe pozitiile.

2, 3, 4, 1, 6, 7, 8, 5

Am sortat primul subsir, mai trebuie sa-l sortam pe al doilea:

2, 3, 4, 1, 6, 7, 8, 5

Incepem cu elementul 1, il vom compara cu fiecare elemnt din sirul nesortat - compus, deocamdata, doar din 3. 3 este mai mare ca 1? Da. Deci 3 si 1 ar trebui sa schimbe pozitiile.

2, 3, 4, 1, 6, 7, 8, 5

2, 1, 4, 3, 6, 7, 8, 5

Urmeaza sa-l comparam pe 7 cu elementele din sirul sortat pentru a stabili unde-l inseram.

 2, 1, 4, 3, 6, 7, 8, 5

Deoarece niciun element nu este mai mare ca 7, acesta isi va pastra pozitia. Trecem la elementul 5.

 2, 1, 4, 3, 6, 7, 8, 5

7 este mai mare ca 5, deci 5 si 7 ar trebuis a schime pozitiile. Sirul nostru arata asa acum:

2, 1, 4, 3, 6, 5, 8, 7

Am sortat cele doua subsiruri, acum putem sa mergem mai departe injumatatind valoarea intervalului. Deci, [2/2] = 1. Cum valoarea intervalului este 1, insemana ca de aici vom avea doar un sigur subsir:

2, 1, 4, 3, 6, 5, 8, 7

Pentru a-l sorta pe acesta vom aplica algortimul e insertion sort clasic. Incepem cu elementul 1, il comparam cu restul elementelor din lista sortata pentru a decide unde-l inseram. Apoi continuam cu elementul 4, repedem procedeul si mergem mai departe cu urmatorul element pana cand sirul este sortat.

Observa ca numarul de subsirui este egal cu valoaera fiecarui interval!

Impelementatia algoritmului

for(gap = n/2; gap > 0; gap /= 2) {
        for(i = gap; i < n; i++) {
            for(j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                temp = v[j + gap];
                v[j + gap] = v[j];
                v[j] =  temp;
            }
        }
    }

   Vom implementa algortimul in limbajul C:

Pe linia 1 avem o bulca for ce initializeaza variabila gap cu valoarea n/2 si va rula pana cand variabila gap va lua valoarea 1 - intrucat conditia ne impune ca gap sa fie strict mai mare ca 0. la fiecare etapa injumatatim valoarea lui gap. Iti este familiara aceasta variabila gap? Exact, aceasta variabila gap este acel interval despre care am discutat mai sus. Probabil te intrebi de ce nu luam partea intreaga  a valorii n/2 inainte de a o stoca in gap. Nu este nevoie, intrucat variabila gap este de tipul intreg, iar acest tip de data nu poate retine numere cu virgula(reale).

Pe linile ce urmeaza avem generalizarea algortimului e insertion sort. Astfel, poti observa ca pe aceste linii sortam elementele aflate la gap distanta. Cand gap va lua valoarea 1, atunci nu vom face decat un insertion sort clasic.

Pe  liniile 4, 5 si 6  interschimbam valoarea elementului curent cu cea a a celui precedent in interval. Aceasta secventa este metoda clasica de swap.

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:

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.