Structuri de Date 2023

Structuri de Date

Curs 6: Quicksort si mediana in O(n)

Cuprins:

Sortare in-place
Quicksort
Quickselect
Mediana in timp liniar
Sortarile bazate pe comparatii sunt Ω(n log n)

1. Sortare in-place

O sortare are proprietatea in-place daca nu are nevoie de spatiu auxiliar de dimensiune O(n).

Intuitia este ca nu avem nevoie de un array auxiliar de aceeasi dimensiune cu intrarea pentru a construi rezultate intermediare. Dar avem voie sa folosim orice cantitate constanta de spatiu, sau chiar extra spatiu cu conditia ca acel spatiu sa fie o(n). Deci spatiu de dimensiune log n sau sqrt n este permis.

Conform definitiei in-place, MergeSort nu este o sortare in-place pentru ca foloseste un array auxiliar de dimensiune O(n) pentru a construi rezultatul interclasarii.
In continuare vom studia QuickSort, care este un algoritm de sortare in-place.

2. QuickSort

Pentru a sorta cu quicksort:

Alegem o valoare din array drept pivot printr-un procedeu arbitrar:
- ultimul/primul element;
- elementul de pe o pozitie generata aleator
Construim o partitie a vectorului in care elementele mai mici decat pivotul sunt in partea din stanga iar elementele mai mari sunt in partea din dreapta.
Repetam acelasi procedeu pe fiecare partitie obtinuta anterior:
- apelam quicksort pe partitia elementelor mai mici
- apelam quicksort pe partitia elementelor mai mari

Efect:

Problema initiala se imparte in stil divide-et-impera
Insa se imparte in doua probleme a caror dimensiune nu o controlam direct.
Pozitia in vectorul sortat a elementului ales drept pivot determina eficienta partitiei (dorim 1/2).

Partitia Hoare

Partitia Lomuto

#include <iostream>#include <ctime>#include <cstdlib>using namespace std;
int alege_poz_pivot(int* v, int st, int dr){    return (st+dr)/2;}
int partition_Hoare(int* v, int st, int dr){    int pivot = v[alege_poz_pivot(v,st,dr)];    int i=st , j=dr;    while (1){        while (v[i]<pivot) i++;        while (v[j]>pivot) j--;        if (i>=j) return j;        swap(v[i],v[j]);        i++;        j--;    }}
int partition_Lomuto(int* v, int st, int dr){    int poz_pivot = alege_poz_pivot(v,st,dr);    swap(v[poz_pivot],v[dr]);    int i=st-1;    for (int j=st;j<dr;j++){        if (v[j]<v[dr])            swap(v[++i],v[j]);    }    swap(v[i+1],v[dr]);    return i+1;}
void quicksort(int* v, int st, int dr){    if (st<dr){        int poz_pivot = partition_Lomuto(v,st,dr);        quicksort(v,st,poz_pivot);        quicksort(v,poz_pivot+1,dr);
    }}
int main(){    srand(time(NULL));    int n=13;    int v[n];    for (int i=0;i<n;i++)        v[i]=rand()%25;
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<endl;
    quicksort(v,0,n-1);
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";
    return 0;}

Complexitate: best case?

Daca pivotul ales pica mereu pe pozitia n/2 atunci:

T(n) = 2 T(n/2) + O(n) rezulta O(n log n) din teorema master.

Complexitate: worst case?

Daca pivotul ales pica mereu pe prima pozitie atunci:

T(n) = T(n-1) + O(n) rezulta O(n^2)

Complexitate QuickSort

Din pacate nu putem folosi teorema master in cazul general:

T(n) = T(α n) + T ( (1-α)n ) + O(n), α ∈ (0,1)

Complexitate medie:

O(n log n).

3. QuickSelect

QuickSelect: Care este al k-lea cel mai mic element dintr-un array?
Este o modificare a lui QuickSort, in care:
- Dupa rezolvarea procedurii de partitie, ignoram partitia in care nu se poate gasi solutia.

#include <iostream>#include <ctime>#include <cstdlib>using namespace std;
int partition(int v[], int st, int dr){    int poz_pivot = alege_poz_pivot(v,st,dr);    swap(v[poz_pivot],v[dr]);    int i = st;    for (int j = st; j <= dr - 1; j++) {        if (v[j] <= v[dr])            swap(v[i++], v[j]);    }    swap(v[i], v[dr]);    return i;}
int kth(int v[], int st, int dr, int k){    if (k > 0 && k <= dr - st + 1) {        int poz_pivot = partition(v, st, dr);        if (poz_pivot - st == k - 1)            return v[poz_pivot];        if (poz_pivot - st > k - 1)            return kth(v, st, poz_pivot - 1, k);        return kth(v, poz_pivot + 1, dr, k - poz_pivot + st - 1);    }    return -1;}
int main(){    srand(time(NULL));
    int n=13;    int v[n];
    for (int i=0;i<n;i++)        v[i]=rand()%25;
    int k=1+rand()%(n-1);    int kvalue=kth(v,0,n-1,k);
    for (int i=0;i<n;i++)        cout<<v[i]<<" ";    cout<<endl;
    cout<<"v["<<k<<"]= ";    cout<<kvalue<<endl;
    return 0;}

Complexitate: best case?

Daca pivotul ales pica mereu pe pozitia n/2 atunci:

T(n) = T(n/2) + O(n) rezulta O(n) din teorema master (cazul 3.1.).

Complexitate medie:

O(n).

Complexitate: worst case?

Daca pivotul ales pica mereu pe prima pozitie atunci:

T(n) = T(n-1) + O(n) rezulta O(n^2)

4. Mediana in O(n) worst case

Problema principala este: cum putem gasi un pivot suficient de bun ca sa garantam O(n) worst case?

1973: Blum, Floyd, Pratt, Rivest, Tarjan -> Propun urmatorul algoritm:

Impartim array-ul in bucati consecutive de cate 5 elemente.
Sortam in timp constant fiecare din cei n/5 mini-array.

Dintre cele 5 elemente sortate ale fiecarui array, al treilea (cel din mijloc) este mediana mini-array-ului.

Teorema: Mediana medianelor array-urilor este un pivot bun.

Proof: In cel mai rau caz mediana medianelor este mai mare decat 30% dintre elemente, deci cea mai slaba partitie este in 3n/10 si 7n/10.

Presupunem ca avem corect localizata mediana-medianelor colorata cu rosu. Atunci:

Exista n/2 mini-array-uri care au mini-mediana mai mica decat valoarea rosie.
In interiorul fiecarui mini-array sortat exista 3/5 elemente mai mici sau egale decat mini-mediana.

=> Exista n/2 * 3/5 = 3n/10 elemente mai mici sau egale decat mediana-medianelor.

5. Sortarile bazate pe comparatii sunt Ω(n log n)

Cu alte cuvinte, orice sortare bazata pe comparatii dureaza cel putin T(n) = Ω (n log n).

Pentru a demonstra, ne gandim cum arata numarul minim de comparatii pentru a sorta un numar fixat de elemente si apoi extrapolam solutia.

Arbore de decizie pentru a sorta 3 elemente:

Pentru n=3 elemente:

Exista n!=6 frunze < 2^h=8

Inaltimea arborelui este h=3.

Descrierea modelului:

Modelam sortarea printr-un arbore in care:
1. fiecare frunza reprezinta ordinea sortata a elementelor
2. a sorta inseamna sa parcurgem un drum de la radacina la frunza corecta
Timpul necesar sortarii (worst case) este cel mai lung drum intr-un astfel de arbore.
Fie un arbore optim care are cel mai scurt drum maxim.
Aratam ca cel mai scurt drum maxim este >= decat log n! ~ n log n

Relatii necesare:

n! <= Numarul de frunze <= 2^h

Numarul de comparatii = h >= log n!

log n! = log 1 + log 2 + ... + log n

aproximatia lui Stirling: log n! = Ω (n log n)

Google Sites

Report abuse