Sortare stabila
Countsort
Radixsort
O sortare se numeste stabila daca ordinea elementelor egale se pastreaza dupa sortare.
La prima vedere proprietatea de stabilitate pare inutila: daca sortam un array de intregi nu ne intereseaza in ce ordine sunt elementele egale pentru ca au aceeasi valoare.
Sortarea stabila se foloseste atunci cand avem de sortat structuri sau tupluri dupa o anumita proprietate a lor. De exemplu, daca sortam structuri student dupa media la structuri de date, sortarea ii poate considera egali d.p.d.v al notei, dar mai exista si restul de informatii de identitate care trebuie purtate impreuna cu elementul care se sorteaza.
O aplicatie la stabilitatea sortarii este sortarea multi-criteriu:
1. sortam dupa cel mai nesemnificativ criteriu
.............................
n. sortam dupa cel mai semnificativ criteriu
Daca sortarea este stabila, ordinea finala pastreaza ordinea:
sortat dupa criteriul n, iar in caz de egalitate:
sortat dupa criteriul n-1, iar in caz de egalitate,
.............................
sortat dupa criteriul 1
Pentru a sorta cu CountSort (metoda naiva):
Numaram fiecare element v[i] intr-un vector de frecvente f[v[i]] (sortam doar intregi pozitivi).
Parcurgem vectorul de frecvente si afisam i de f[v[i]] ori
Varianta imbunatatita:
Numaram fiecare element v[i] intr-un vector de frecvente f[v[i]] (sortam doar intregi pozitivi).
Parcurgem vectorul de frecvente adunam f[j] peste f[j+1]
Astfel, f[j] contine pozitia din vectorul sortat unde se termina sirul de valori egale cu j.
Parcurgem vectorul initial si punem v[i] la pozitia f[v[i]]-1 in output, dupa care f[v[i]] scade cu 1
Varianta stabila:
Numaram fiecare element v[i] intr-un vector de frecvente f[v[i]] (sortam doar intregi pozitivi).
Parcurgem vectorul de frecvente adunam f[j] peste f[j+1]
Astfel, f[j] contine pozitia din vectorul sortat unde se termina sirul de valori egale cu j.
Parcurgem vectorul initial INVERS si punem v[i] la pozitia f[v[i]]-1 in output, dupa care f[v[i]] scade cu 1
Complexitatea timp: worst case = best case = medie = O(n+max(v))
Complexitatea spatiu: O(n+max(v))
Vrem sa sortam: [400000000, 5, 8]
Trebuie sa alocam un vector de frecventa de dimensiune 400000000 si sa-l initializam cu 0.
Deci CountSort este eficient doar pentru max(v) suficient de mic.
radix = baza de reprezentare a numarului
Pentru a sorta un array v cu RadixSort vom sorta repetat folosind CountSort stabil:
dupa cea mai nesemnificativa cifra (in raport cu baza aleasa)
dupa a doua cea mai nesemnificativa cifra (in raport cu baza aleasa)
..........................
k. dupa cea mai semnificativa cifra (in raport cu baza aleasa)
Apare un trade-off timp-spatiu:
(Timp) Numarul de sortari CountSort aplicate este dat de maxlen = log_radix(max(v)).
(Spatiu) Numarul de elemente din vectorul de frecventa al lui CountSort = numarul de cifre din baza aleasa = radix
maxlen = log_radix(max(v))
Fiecare CountSort se apeleaza de maxlen ori, si parcurge 3n+2radix operatii.
Complexitatea timp: O((n + radix) * maxlen)
Fiecare CountSort aloca un array de dimensiune n si un array de dimensiune radix.
Complexitatea spatiu: O(n + radix)
Daca consideram radix ca fiind constant sau cel mult in O(n), atunci ajungem la:
Complexitatea timp: O(n * maxlen)
Complexitatea spatiu: O(n)
Spatiul necesar creste odata cu cresterea radix-ului dupa care facem radix sort, iar numarul de treceri de sortare scade.