Comparatie intre diferite tipuri de sortari avansate. - Concluzii.
Breviar teoretic
BrickSort
BucketSort
CountSort
RadixSort
Bibliografie
Concluzii
Contactati-ma !
Iata cateva concluzii finale desprinse din concluziile de pe parcurs:
1. Daca se doreste un algoritm usor de memorat si de implementat, se va folosi BubbleSort. Se precizeaza complexitatea algoritmului: O(n2) si faptul ca sortarea se face in situ pe baza de comparatii de chei.
2. Daca se doreste studierea unui algoritm avansat de sortare dar care nu aduce reale imbunatatiri fata de BubbleSort, desi modul sau de lucru este foarte interesant, se va implementa BrickSort. S-a demonstrat ca complexitatea sa este: O(n2*ln(n)) si faptul ca sortarea se face in situ pe baza de comparatii de chei. Este oare BrickSort mai bun decat BubbleSort in ceea ce priveste complexitatea? Raspunsul este afirmativ dar nu foloseste la nimic pentru ca acesta este: Cand n<=2, BrickSort este mai bun decat BubbleSort. Deci este intotdeauna de preferat BubbleSort in locul BrickSort.
3. Daca avem un set de elemente in intervalul [0,1) uniform distribuite in acest interval, sau daca putem ajusta intervalul in care se afla numerele noastre de sortat la un interval [0,1) (adica daca impartim toate numerele noastre cu exceptia celui maxim la cel maxim si obtinem o distributie uniforma in intervalul [0,1)) putem aplica BucketSort cu succes. Am demonstrat ca complexitatea lui este O(n) si ca sortarea nu se face in situ dar se realizeaza prin comparatii de chei. Dezavantajul este restrictia de lucru, dezavantaj major.
4. Daca se doreste un algoritm usor de memorat si de implementat, cu sortare bazata pe comparatii de chei, dar care nu este realizata in situ (un algoritm usor si foarte didactic), se va folosi CountSort. Am demonstrat ca complexitatea algoritmului este O(n2).
5. Daca dorim o sortare rapida de numere pozitive, codificabile pe un numar de biti cunoscut, atunci vom folosi RadixSort. Acesta este un algoritm rapid, datorita complexitatii sale O(n), si care are un numar mic de inconveniente: numerele sa fie pozitive si codificabile binar pe un numar de biti bine cunoscut, si, totodata un spatiu relativ mai mare de memorie ocupata deoarece sortarea nu se realizeaza in situ. Sortarea nu se realizeaza pe comparatii de chei, ci prin grupare de chei.
6. Concluzie finala: dintre algoritmii de studiat, RadixSort este cel mai bun din punct de vedere al rapiditatii si cerintelor limitative, iar BubbleSort este cel mai usor de implementat algoritm care nu cere resurse (memorie) suplimentare si nici nu prevede necesitatea ca numerele de sortat sa fie pozitive.
Pentru a rula pagina la inceput (la meniu) dati un click aici.