Comparatie intre diferite tipuri de sortari avansate. - Brick Sort.

Breviar teoretic
BrickSort
BucketSort
CountSort
RadixSort
Bibliografie
Concluzii
Contactati-ma !

        Pentru inceput voi prezenta algoritmul de sortare prin insertie (tehnic numit InsertionSort). In ce consta algoritmul:fie un vector V cu n elemente pe pozitii de la 0 la n-1 si presupunem ca facem o sortare crescatoare. Pornim de la primul element V[0]. Cu el singur nu avem ce face, asa ca il luam si pe urmatorul V[1]. Daca V[1]<V[0], atunci le interschimbam, daca nu, nu. La un pas oarecare i (intre 2 si n) trebuie ca toate elementele aflate pe pozitiile inferioare lui i sa fie mai mici sau egale decat elementul de pe pozitia i. Algoritmul in pseudocod este:

pentru(j=2;j<=n;j<-j+1)
   {cheie<-V[j];
    i<-j-1;
    cat timp (i>=0 si V[i]>cheie)
     {V[i+1]<-V[i];
      i<-i-1;
     }
   V[i+1]<-cheie;
   }
Gata!

        Se preia complexitatea algoritmului ca fiind in cazul mediu C=O(n²).
        Vom dezvolta acest a algoritm la unul si mai bun din punct de vedere al complexitatii. Vom face urmatoarea observatie: In cazul unei sortari directe, elementele efectueaza salturi pe distante mici (distante din punct de vedere al indicelui). Deci daca se reuseste crearea unui algoritm in care elementele sa efectueze salturi pe distante mari, complexitatea se va imbunatati. Iata un exemplu: fie un vector V de n elemente situate pe pozitii de la 0 la n-1. Presupunem de asemenea ca n este par. Iata in ce consta algoritmul: se imparte vectorul in fragmente de 2 elemente. Se sorteaza elementar (prin interschimbare daca este cazul) fiecare fragment. Apoi se imparte vectorul (sortat deja pe bucatele) in fragmente de 4 elemente. Se sorteaza fiecare fragment. Se obtin deci bucatele sortate de dimensiuni mai mari. Se merge mai departe cu fragmente de 8 elemente, 16, etc. In final tot vectorul va fi sortat. Se preia complexitatea acestui algoritm ca fiind C=O(n^3/2). De asemenea se cuvine si o observatie: acest ultim algoritm se numeste ShellSort si a fost propus de catre Donald L. Shell in 1959 pe baza acelorasi considerente pe care le-am prezentat in aceasta descriere rapida.

        Se pune problema daca acest program se mai poate imbunatati din punct de vedere al complexitatii. Ajungem la destinatia comparatiei intre algoritmi: BrickSort. Acest algoritm se bazeaza pe algoritmul ShellSort dar proprietatea de h-sortare este asigurata de folosirea algoritmului BubbleSort si nu a algoritmului InsertionSort. Se va folosi un set de numere h date de relatia: h(0)=1, h(k+1)=3h(k)+1 pentru k=1 ... l unde h(l)<=lungime(v). Algoritmul in pseudocod este:

BrickSort(int v[])
   {k<-1;
   cat timp(k<lungime(v) executa: k<-3*k+1;
   cat timp(k>=1) executa:
     {k<-(k-1)/3;
     BubbleSort(v,k);
     }
   }
   Gata !

Dar cine este BubbleSort(v,k)? Algoritmul BubbleSort in pseudocod este:

BubbleSort(int v[],int h)
   {pentru(k=1;k<=h;k<-k+1) executa:
     {i<-lungime(v);
      cat timp(i>=1) executa:
       {j<-k;
        cat timp(j+h<=i) executa: daca(v[j]>v[j+pas]) atunci v[j] interschimba cu v[j+pas]
        j<-j+h;
        i<i-h;
       }
     }
   }
   Gata!

        Codul algoritmului BrickSort in C++ parametrizat se afla aici
        Codul algoritmului BrickSort in J++ se afla aici

        Corectitudinea algoritmului consta in demonstrarea corectitudinii algoritmilor ShellSort si BubbleSort, adica: pentru BubbleSort pornim de la ce face algoritmul - se parcurge un vector de la indicele minim catre indicele maxim si se interschimba doua elemente daca acestea sunt plasate invers (adica numarul mai mic pe indice mai mare). Evident, pe ultima pozitie a vectorului (V[n-1]) va fi plasat elementul de valoare maxima iar pe pozitia 0 (V[0]) va fi plasat elementul de valoare minima. Deci algoritmul BubbleSort este corect. Acum pentru ShellSort: cum acest algoritm se bazeaza pe o sortare elementara (dintre doua elemente) urmata de sortari la un nivel mai inalt, acest algoritm exte corect.

        Complexitatea algoritmului consta in "legarea" formulelor de complexitate pentru BubbleSort si ShellSort (formule presupuse cunoscute pentru ca nu fac obiectul acestui proiect). Pentru BubbleSort complexitatea este:

dar la noi numarul de elemente pentru care se aplica BubbleSort este n/k. Asadar formula devine: N_c=n*(ⁿ/_k-1)/2. Atunci numarul total de comparatii pe chei (pentru toate valorile k) este:

. Dar suma poate fi aproximata (pentru valori mari ale lui l) astfel:

. Dar am precizat la inceput ca valoarea l trebuie aleasa astfel incat h(l)<=n, adica 3*l+1<=n, deci l=[(n-l)/3]. Expresia devine:

. Acum inlocuind in expresia lui N_c se obtine:

.
Asadar, complexitatea algoritmului este: O(n²*ln(n)).

Pentru a rula pagina la inceput (la meniu) dati un click aici.