Comparatie intre diferite tipuri de sortari avansate. - Breviar teoretic.
Breviar teoretic
BrickSort
BucketSort
CountSort
RadixSort
Bibliografie
Concluzii
Contactati-ma !
In viata de zi cu zi intalnim sortari (mai mult sau mai putin evidente), acest fapt fiind o consecinta a necesitatii crearii unor prioritati pentru obiecte, fenomene sau chiar notiuni abstracte (numere, etc.). Odata cu aparitia sistemelor informatice (bazate pe marimi numerice), sortarile din lumea reala au devenit sortari de diferite chei (care pot fi numerice, de caractere, etc.). De aceea au aparut si algoritmii de sortare, care sunt implementari informatice ale algorimilor pe care omul si chiar animalele ii aplica in viata de zi cu zi. Diferenta consta in faptul ca algoritmii de sortare pe calculator sunt rigurosi (adica corectitudinea lor este demonstrabila si nu ezita, asa cum face de exemplu un copil mic care sorteaza cuburile dupa culori (nestiind ca o culoare reprezinta o lungime de unda a fotonului)).
Cel mai usor se pot explica algoritmii de sortare pe numere, pentru ca oricine stie ca 3 este mai mic decat 5 (ar fi greu sa spunem de exemplu ca rosu este mai mic ca violet pentru ca ar trebui sa explicam in prealabil ca frecventa radiatiei rosii este mai mica decat frecventa radiatiei violet, ambele din spectrul vizibil). Asadar in continuare vor fi explicati algoritmi bazati pe sortari de numere.
Pentru inceput, cel mai usor de inteles algoritm de sortare (numit in inginerie BubbleSort pentru ca se aseamana cu bulele de gaz din apa carbogazoasa: cand turnam apa carbogazoasa intr-un pahar transparent, putem observa ca bulele mai mari in diametru se ridica (din cauza fortei arhimedice mai mari) mai repede decat bulele mai mici in diametru). In ce consta algoritmul: fie un sir de numere plasat intr-un vector cu indici de la 0 la n-1 si presupunem ca facem sortarea numerelor din vector in ordine descrescatoare. Cum putem face sortari ? O prima metoda este sa construim un alt vector cu tot atatea pozitii (n) si sa parcurgem vectorul initial extragand maximul pe care sa il inseram in vectorul creat (si il marcam in vectorul initial, ca sa nu il mai luam in calcul). Apoi se mai parcurge vectorul initial extragandu-se maximul pe care il marcam si il inseram in vectorul creat. Se continua algoritmul pana la epuizarea numerelor din vectorul initial (adica pana cand sunt toate numerele marcate).
Introducem notiunea de COMPLEXITATE ca fiind numarul de pasi pe care ii executa algoritmul astfel: daca expresia numarului de pasi este polinomiala, se va considera termenul dominant si neglijandu-se coeficientul numeric. Analog si la expresie exponentiala. Adica: daca expresia este numarul de pasi N=2*n3*en+7*n+1 (unde n este numarul de elemente si e este baza logaritmilor nepperieni), atunci complexitatea C=n3*en. Evident, se doreste o complexitate cat mai mica.
In cazul exemplului dat anterior complexitatea este: C=n2, pentru ca se fac n parcurgeri ale sirului initial format din n elemente. Complexitatea este mare. Un alt algoritm este astfel: consideram doi indici care parcurg sirul initial (pentru i de la 0 la n-1 pentru j de la 0 la n-1). Daca numarul e pe pozitia i si numarul de pe pozitia j nu corespund ca ordine, ei se vor interschimba. Evident, complexitatea este tot C=n2; explicatia: pentru fiecare valoare a lui i se parcurge j de la 0 la n-1. Avantajul acestei a doua metode este alocarea unui spatiu de memorie considerabil mai mic (numai o singura pozitie pentru interschimbare, in loc de un vector intreg). Concluzia este ca acest al doilea algoritm desi nu imbunatateste complexitatea, este mai bun pentru ca se ocupa mult mai putina memorie.
Sa vedem cum putem imbunatati (daca se poate) complexitatea. Vom imparti vectorul initial (sa zicem ca n este par) in doi vectori de n/2 elemente. Sortam intai prima parte cu o complexitate: C1=(n/2)2 si apoi si a doua parte cu o complexitate: C2=(n/2)2. Apoi interclasam elementele celor doua fragmente de vector intr-un vector de aceeasi dimensiune. Complexitatea interclasarii este: C3=n. Deci complexitatea finala este: C=C1*C2*C3=n3/4. Evident, mai proasta. Dar daca gandim si mai profund si presupunem ca avem segmentele de vecor initial deja sortate, complexitatea intregului algoritm devine: C=C3, foarte buna. Deci daca reusim sa sortam mai simplu cele doua fragmente de vector initial, sortarea intregului vector devine foarte rapida. Se poate oare sa sortam mai eficient fragmentele de vector? Raspunsul este DA. Iata de ce: Daca presupunem ca fragmentele sunt alcatuite din doar 2 elemente (adica n=4), sortarea se reduce la interschimbarea (sau nu) a celor doua elemente. Deci am dovedit ca putem crea o functie recursiva care sa tot divida vectorul initial pana la fragmente primitive (cu 2 elemente), urmate de interschimbari si interclasari pana la crearea unui vector final ordonat.
In aceasta pagina am aratat ca algoritmii simpli pot fi imbunatatiti din punct de vedere al complexitatii. O mica observatie: de obicei imbunatatirea unui algoritm intr-un punct (de exemplu imbunatatirea complexitatii) atrage dupa sine inrautatirea algoritmului in alt punct (de exemplu marirea semnificativa a spatiului de memorie ocupat).
Notatie: a<-b inseamna incarca valoarea variabilei b in variabila a.
Pentru a rula pagina la inceput (la meniu) dati un click aici.