Structuri de Date 2023

Structuri de Date

Curs 7: Countsort, Radixsort

Cuprins:

Sortare stabila
Countsort
Radixsort

1. Sortare stabila

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.

Sortarea multi-criteriu:

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

2. CountSort

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

Complexitate CountSort

Complexitatea timp: worst case = best case = medie = O(n+max(v))

Complexitatea spatiu: O(n+max(v))

#include<iostream>using namespace std;void countSort(int v[],int n,int BUCKETS){    int count[BUCKETS], i;    for (i=0; i<BUCKETS; i++)        count[i]=0;    for (i=0; i<n ; i++)        count[v[i]]++;//adunarea la dreapta produce pozitiile din vectorul sortat ale fiecarui numar    for (i=1; i<BUCKETS; i++)        count[i] += count[i-1];
    int out[n];//pentru asigurarea stabilitatii parcurgem invers    for (i=n-1; i>=0; i--) {        out[count[v[i]]-1] = v[i];        count[v[i]]--;    }    for (i = 0; i<n ; i++)        v[i] = out[i];}
int main(){    int v[] = {28, 21, 63, 69, 29, 5, 99, 4, 56, 25, 30, 58, 16, 65, 37, 38, 84, 79, 47, 5, 89, 38, 71, 36, 61, 68, 33, 76, 2, 52};    int n=sizeof(v)/sizeof(int);    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<endl;
    countSort(v,n,100);
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    return 0;}

De ce nu prea folosim CountSort?

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.

3. RadixSort

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

Complexitate RadixSort

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.

#include <iostream>using namespace std;
int getMax(int v[], int n){    int mx = v[0];    for (int i = 1; i < n; i++)        if (v[i] > mx)            mx = v[i];    return mx;}
void countSort(int v[], int n, int exp){    int out[n];    int i, count[10];    for (i=0; i<10; i++)        count[i]=0;    for (i=0; i<n; i++)        count[(v[i] / exp) % 10]++;//adunarea la dreapta produce pozitiile din vectorul sortat ale fiecarui numar    for (i=1; i<10; i++)        count[i] += count[i-1];//sortam dupa cifra indicata de exp 1=unitati, 10=zeci, etc.    for (i=n-1; i>=0; i--) {        out[count[(v[i]/exp)%10]-1] = v[i];        count[(v[i]/exp)%10]--;    }    for (i=0; i<n; i++)        v[i] = out[i];}
void radixSort(int v[], int n){    int m = getMax(v, n);
    for (int exp = 1; m / exp > 0; exp *= 10){        countSort(v, n, exp);        cout<<"[exp = "<<exp<<"]\t";        for (int i=0;i<n;i++)            cout<<v[i]<<" ";        cout<<endl;    }}
int main(){    int v[] = {28, 21, 63, 69, 29, 5, 99, 4, 56, 25, 30, 58, 16, 65, 37, 38, 84, 79, 47, 5, 89, 38, 71, 36, 61, 68, 33, 76, 2, 52};    int n=sizeof(v)/sizeof(int);    for (int i=0;i<n;i++)        cout<<v[i]<<" ";        cout<<endl;    radixSort(v, n);    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    return 0;}

Google Sites

Report abuse