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

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

        Acest algoritm este aplicabil (in termeni standard) pentru date situate (distribuite) relativ uniform (cat mai uniform) in intervalul [0,1). Inainte de a da modul de lucru al algoritmului, se va face o mica observatie: daca avem de lucru cu numere pozitive supraunitare atunci iata ce se intampla - fie A si B doua numere pozitive si supraunitare astfel incat A>=B. Atunci A^-1<=B^-1. Deci ca sa putem sorta numere pozitive si supraunitare ce indeplinesc conditia ca inversele lor sa fie cat mai uniform distribuite in intervalul [0,1) vom proceda astfel: sortam inversele numerelor initiale cu ajutorul BucketSort si apoi le citim in ordine inversa celei obtinute prin sortare, reinversandu-le.
        Acum in ce consta algoritmul: Se imparte intervalul de lucru, adica [0,1) in n fragmente egale numite galeti (de unde si denumirea de BucketSort). Cum numerele de sortat sunt cat mai uniform distribuite in intervalul de lucru, rezulta ca in fiecare galeata se vor afla cam acelasi numar de elemente (numere). Se sorteaza elementele din fiecare galeata si se obtin astfel galetile sortate. Prin reunirea tuturor galetilor sortate se obtine in urma interclasarii sirul sortat de numere. Cateva observatii trebuie facute: daca prin algoritm trebuie sa sortam fiecare galeata si apoi sa interclasam galetile, putem reduce cele doua operatii (sortarea si interclasarea) la alte doua operatii echivalente: Sortarea prin insertie (care efectueaza sortare si o parte a interclasarii - vezi pentru mai multe detalii breviarul teoretic de la BrickSort unde este explicat mai pe larg conceptul de sortare prin insertie) si Concatenarea de intervale (intervale rezultate in urma sortarii prin insertie a galetilor). In continuare vom prezenta algoritmul in pseudocod in urmatoarea ipoteza: fie un vector V in care se incarca numerele de sortat (acestea respecta conditiile BucketSort - sunt subunitare si cat mai uniform distribuite). Fie un vector temporar de galeti GAL ale carui elemente sunt liste. Se presupune ca pentru operatii cu liste sunt predefiniti operatorii: InsertLista(element,lista) (insereaza elementul element in lista lista) si ConcatLista(lista1,lista2,lista3,...,listan) (concateneaza listele date ca parametri). Atunci algoritmul este:

BucketSort(V)
   {n<-lungime(V);
    pentru(i<-1;i<=n;i<i+1) executa: InsertLista(V[i],GAL[trunc(n*V[i])]; //trunc=parte intreaga
    pentru(i<-0;i<n;i<i+1) executa: InsertionSort(GAL[i]);
    ConcatLista(GAL[0],GAL[1],GAL[2],...,GAL[n]);
   }
   Gata !

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

        Corectitudinea algoritmului este aproape evidenta datorita faptului ca in acest algoritm se folosesc doi algoritmi despre care se stie ca sunt corecti: InsertionSort si Concatenare. Totusi, trebuie sa demonstram ca si folosirea lor este corecta. Daca doua elemente din vectorul V se afla in aceeasi galeata, ele sunt deja sortate in urma aplicarii InserionSort, deci corectitudinea este evidenta. Mai trebuie analizat cazul in care doua elemente din V nu se afla in aceeasi galeata. Deci cele doua elemente V[i] si V[j] vor fi plasate in doua galeti GAL[i'] si GAL[j']. Daca i'<j', atunci la concatenarea listelor (galetilor) elementele subintervalului i' vor fi inaintea elementelor intervalului j' in lista finala, adica V[i] va fi inaintea lui V[j] pentru ca V[i]<=V[j] (ceea ce rezulta din faptul ca i'=trunc(n*V[i]) <= trunc(n*V[j])=j'. Deci algoritmul este corect.

        Complexitatea algoritmului consta in determinarea complexitatii InsertionSort in acest caz. Se observa ca in afara acestui aspect, toate celelalte etape ale algoritmului au complexitatea O(n). Se presupune cunoscuta complexitatea metodei de sortare prin insertie: O(n²). Cum aceasta sortare se aplica pentru fircare galeata in parte, fie n_i numarul elementelor din galeata GAL[i]. Atunci, complexitatea sortarii galetii GAL[i] este C_i=O(n_i²). Sa vedem daca mai putem oarecum sa rafinam aceasta expresie pentru ca ea sa devina mai precisa. Pentru aceasta apelam la proprietatea ca elementele pentru aplicarea BucketSort sunt cat mai uniform distribuite in intervalul de lucru. Rezulta ca probabilitatea p ca un element oarecare sa se afle in galeata GAL[i] este 1/n. Deci probabilitatea ca n_i=k are o distributie binomiala si deci variatia lui n_i este 1-¹/_n. Deci timpul asteptat de sortare a tuturor elementelor din toate subintervalele (adica complexitatea sortarii prin insertie) este in acest caz teta(n). Rezulta astfel complexitatea intregului algoritm: O(n).

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