Sortare in-place
Quicksort
Quickselect
Mediana in timp liniar
Sortarile bazate pe comparatii sunt Ω(n log n)
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.
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).
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.
Daca pivotul ales pica mereu pe prima pozitie atunci:
T(n) = T(n-1) + O(n) rezulta O(n^2)
Din pacate nu putem folosi teorema master in cazul general:
T(n) = T(α n) + T ( (1-α)n ) + O(n), α ∈ (0,1)
O(n log n).
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.
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.).
O(n).
Daca pivotul ales pica mereu pe prima pozitie atunci:
T(n) = T(n-1) + O(n) rezulta O(n^2)
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.
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.
Modelam sortarea printr-un arbore in care:
fiecare frunza reprezinta ordinea sortata a elementelor
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
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)