| Hemorrhoid pain relief

Algoritmi.

Prezentarea algorimului de sortare rapida (quicksort).

Cuprins:
1. Definirea sortarii rapide.
2. Algoritmul sortarii rapide.
3. Versiune de sortare rapida care executa o partitionare pe loc.
4. O implementare in limabajul C a metodei de sortare rapida care alege pivotul.
5. Sortarea rapida in paralel.
6. Competitia sortarii rapide cu alti algoritmi de sortare.
7. Analiza principiului de sortare rapida.
8. Analiza complexitatii metodei de sortare rapida.
9. Analiza sortarii rapide cand are o complexitate medie.
10. Utilizarea spatiului de memorie in cadrul sortarii rapide.

1. Definirea sortarii rapide (quicksort). >>>

Algoritmul Quicksort continua in acest moment cu procesarea celor 2 sectoare. In fiecare din acest sector se alege iar un pivot si se repeta procesul se separare a valorilor in functie de pivot. Se continua, pana cand subsectoarele devin destul de mici pentru a fi sortate usor prin alte metode. Performanta intregului algoritm depinde de modul in care se selecteaza pivotul. Cel mai ineficient scenariu ar fi cand datele sunt deja sortate. Cel mai mare dintre primele doua elemente va divide pur si simplu datele intr-o serie de 1 element si o a doua serie de (x-1) elemente. Aceasta va cauza functionarea algoritmului in n² miscari.

O alta limitare a Quicksort este ca desi se comporta bine pentru serii mari de date, pentru serii mici are o comportare slaba.
Cea mai buna si intalnita eficienta de functionare a Quicksort este de forma :

Sortarea poate fi optimizata prin folosirea unor alternative de genul sortarii prin insertie in cazul seriilor mici de date (dupa aplicarea algoritmului Quicksort pana la un anumit punct).

2. Algoritmul sortarii rapide. >>>

Sortarea rapida (quicksort) sorteaza datele dupa principiul "imparte si stapaneste" (divide et impera) pentru a segmenta o lista in doua sub-liste.

Pasii care realizeaza aceasta divizare sunt:

1. Se alege un element, care se va numit pivot din elementele listei.
2. Se reordoneaza lista astfel incat toate elementele care detin o valoare mai mica decat valoarea elementului pivot (care este valoare de mijloc a listei) se vor pozitiona inaintea elementului pivot, si deasemeni elementele care au o valoare mai mare decat valoarea elementului pivot se vor pozitiona dupa elementul pivot (chiar si cu elementele cu valori egale se va proceda asa).Dupa aceasta aranjare a alementelor (partitionare) in functie de pivot,si pivotul va fi pozitionat la locul potrivit.Aceasta operatie poarta denumirea de partitionare.
3. Se sorteaza recursiv sub-lista care detine elementele cu valorile mai mici decat valoarea elementului de mijloc (pivotul), apoi se sorteaza sub-lista care contine elementele cu valori mai mari decat valoarea elementului de mijloc.

Cazul de baza a unei recursivitati sunt listele de dimensiune zero sau unu, care sunt si ele sortate.Acest principiu este o varianta a mai putin cunoscutei sortari numita "hillsort".Algoritmul functioneaza rapid deoarece se pozitioneaza cel mult un element la locul lui final la fiecare iteratie a sortarii.

Explicand algoritmul intr-un pseudocod implementat in limbajul Pascal acesta poate fi scris astfel:

function sortare_rapida(q)
var lista mic, pivotul_listei, mare
if lungimea(q) < = 1
return q
selecteaza un element pivot de la q
for fiecare x din q
if x < pivot atunci aduce pe x in partitia cu valori mici
if x = pivot atunci x este pivotul_listei
if x > pivot atunci aduce pe x in partitia cu valori mari
return
concatenaeza(sortare_rapida(mic), pivotul_listei, sortare_rapida(mare))

Se observa caci principiul sortarii se bazeaza pe examinarea elementelor prin compararea lor cu alte elemente, de aceea sortarea rapida face parte di familia sortarilor prin comparatie.

3. Versiunea care executa o partitionare "pe loc". >>>

Dezavantajul versiunii simple prezentate in imaginea de alaturi este ca necesita un spatiu de memorie suplimentar care sa aiba Ù(n) locatii, acesta influentand negativ practicare sortarii rapide.Dupa acest principiu este inspirata si sortarea prin interclasare (merge sort).Acest spatiu suplimentar de memorie alocat poate influenta negativ viteza de sortare al algoritmului chiar daca datele care se sorteaza sunt in memoria CACHE.
Implementarea de mai jos reprezinta o versiune de algoritm de sortare rapida mult mai complicat, care poate achizitiona un spatiu de memorie care sa aiba un numar de O(logn) locatii in cazul in care se alege un element pivot corect:

Acesta este un algoritm de partiutionare "pe loc".El imparte (partitioneaza) structura tabloului in doua parti care vor fi reprezentate prin termenii de stanga si dreapta, in care se pun toate elementele mai mari sau egale cu tablou[indexul_pivotului] la inceputul sub-tabloului stang, lasand ca elementele cu valori mai mari sa le urmeze.In acest proces algoritmul va cauta pozitia finala pentru elementul pivot (sau pivotul).Adica, el pozitioneaza temporar la sfarsitul oricarei dintre cele doua sub-tablouri rezultate in urma partitionarii tabloului original, atat timp cat un al element este potrivit pentru a fi pivot.Insa, deoarece au loc multe interschimbari, lista sortata va avea forma finala avand aceleasi elemente ca si lista initiala.In trebuie mentionat faptul ca un element isi poate schimba fregvent locatia pana sa ajunga la pozitia lui finala.

Iata un exemplu de algoritm de sortare mult mai simplu:

function sortare_rapida(tablou, stanga, dreapta)
if dreapta < stanga
selecteaza o locatie pentru pivot (ex. locatie_pivot = stanga)
locatia_noua_pivot := partitioneaza(tablou, stanga, dreapta, locatie_pivot)
sortare_rapida(tablou, stanga, locatia_noua_pivot-1)
sortare_rapida(tablou, locatia_noua_pivot+1, dreapta)

4. O versiune de implementare in limbajul C care alege pivotul pentru o sortare rapida. >>>

Algortimii care pot sa aleaga pivotul potrivit sunt mult mai eficienti decat algoritmii care nu dispun de aceasta functie numai atunci cand functia de alegere a pivotului nu reprezinta un procedeu complex.Urmatorul cod scris in limbajul C este mult mai eficient din punct de vedere aritmetic, pentru ca pozitioneaza elementele cu valori mai mic decat elementul cu valoarea medie (pivotul) a tablouluiinaintea acestuia, iar elementele mai mari ca si valoarea elementului cu valoare medie din tablou se vor pozitiona dupa acesta.Valoarea elementului din mijlocul tabloului, din punct de vedere aritmetic, este cuprinsa intre elementul cu cea mai mica valoare din tablou si elementul cu valoarea cea mai mire din tablou.Astfel procedul algoritmului de sortare rapida se aplica numai elementelor cuprinse intre elementul cu cea mai mica valoare din tablou si elementul cu valoarea cea mai mare din tablou, aceasta deoarece elementul cu valoarea cea mai redusa din tablou si elementul cu cea mai mare valoare din tablou sunt situate in locatia corecta.

#include 
#include 
/* Pentru a avea mai multe numere in tablou se modifica valoarea
* situata dupa "ELTS".Se pot scrie valori mai mari decat este necesar,
*insa pentru locurile ramase neocupate in tablou se va afisa cifra 0.*/
#define ELTS 10
void inlocuieste(int *, int *);
void sortarea_rapida(int [], int, int);
void afiseaza_numerele(int [], int);
int main(void)
{
int nums[ELTS] = { 7, 210, 903, 57, 292, 792, 37, 103, 819, 649};
puts("Tabloul nesortat:");
afiseaza_numerele(nums, ELTS);
sortarea_rapida(nums, 0, ELTS - 1);
puts("Tabloul sortat devine:");
afiseaza_numerele(nums, ELTS);
return 0;
}
/*aceasta functie se utilizizeaza pentru a sorta valorile a doua variabile */
void inlocuieste(int *a, int *b)
{
int c = *a;
*a = *b;
*b = c;
}
/* nums[] -tabloul cu numerele care trebuiesc sortate
* primul - locatia primului element care trebuie sortat
*ultimul - locatia ultimului element care trebuie sortat */
void sortarea_rapida(int nums[], int primul, int ultimul)
{
int i,pivot,stanga,dreapta,treceri = ultimul - primul,mijloc;
/* nu ruleaza daca in tabloul de numere exista numai un element */
if (treceri > 0)
{
/*Instructiunea "if" care urmeaza verifica si aranjeaza elementele
* cu valori mici la inceput,
*iar elementele cu valori mari la sfarsitul tabloului. */
if (nums[primul] > nums[ultimul])
inlocuieste(&nums[primul], &nums[ultimul]);
if (treceri > 1)
{
for (i = primul + 1; i < ultimul; i++)
{
if (nums[i] < nums[primul])
inlocuieste(&nums[i], &nums[primul]);
else if (nums[i] > nums[ultimul])
inlocuieste(&nums[i], &nums[ultimul]);
}
if (treceri > 2)
{
mijloc = (nums[primul] + nums[ultimul]) / 2;
pivot = nums[primul + 1];
/*Bucla "for" care urmeaza descopera valoarea elementului pivot. */
for (i = primul + 2; i < ultimul; i++)
{
if (abs(nums[i] - mijloc) < abs(pivot - mijloc))
pivot = nums[i];
}
stanga = primul + 1;
dreapta = ultimul - 1;
/* Dupa terminare buclei urmatoare
*(la o singura trecere a metodei sortare_rapida),
* "dreapta" indica locatia elementului pivot... */
while (stanga < dreapta)
{
while (nums[stanga] < pivot)
stanga++;
while (nums[dreapta] > pivot)
dreapta--;
if (stanga < dreapta)
inlocuieste(&nums[stanga], &nums[dreapta]);
if (nums[stanga] == pivot && nums[dreapta] == pivot)
stanga++;
}
/* ...aceasta deoarece sortara rapida este folosita recursiv
* in tabloul de numere incepand de la punctul
* "primul + 1" to "dreapta - 1" si
* de la punctul "dreapta + 1" to "ultimul - 1". */
sortarea_rapida(nums, primul + 1, dreapta - 1);
sortarea_rapida(nums, dreapta + 1, ultimul - 1);
}
}
}
}
/* Se afiseaza valorile numerelor din tablou */
void afiseaza_numerele(int nums[], int lungime_tablou)
{
int x;
for (x = 0; x < lungime_tablou; x++)
{
printf("%d%s", nums[x], x + 1 != lungime_tablou ? ", " : "\n");
}
}

5. Sortarea in paralel. >>>

Asemeni ca sortarea prin interclasare (mergesort), sortarea rapida poate aborda un procedeu de sortare pararela pentru ambele partitii de date, deoarece este un algoritm de natulra "imparte si stapaneste".Operatiile de partitionare individuala poate deveni un procedeu complex, insa daca se impart aceste partitii in diferite sectiuni atunci lista poate fi sortata in paralel.Dace se detine un numar de p procese, atunci se poate imparti o lista care contine un numar de nelemente intr-un numar de p sub-liste intr-un timp mediu de È(n),atunci sortarea fiecarei sub-liste se va efectua intr-un timp mediu definit prin functia O((n/p) log(n/p)).Ignorand faptul ca avem de sortat O(n) procese, atunci sortarea rapida care abordeaza un algoritm de sortare in pararela partitiilor poate performa un timp liniar de executie.Insa daca se considera ca avem de sortat un numar de È procese, atunci se va obtine un timp de sortare a intregii liste definit prin functia (O(n).

Un avantaj al sortarii rapide care abordeaza un algoritm de sortare paralele a partitiilor este ca nu necesita o sincronizare a porceselor de sortare.Daca intr-o lista se desfasoara simultan mai multe procese de sortare, atunci un nou proces de sortare poate sa abordeze cu intarziere o sub-lista valabila pentru procesul lui de sortare, fara sa depinda de celelalte procese de sortare.Cand toate procesele de sortare sunt finalizate atunci lista este sortata.

Dace se detine un alt algoritm de sortare in paralel mult mai complex, atunci se poate performa o limita a timpul de sortare mult mai buna.De exemplu in 1991 David Powers a descris o metoda de sortare in paralel care poate opera intr-un timp de O(log n) care detinea un numar prea mic de procese valabile sa sorteze implicti toate partitiile rezultate in urma alegerii elementului pivot.

6. Competitia sortarii rapide cu alti algoritmi de sortare. >>>

sortarea rapida este o versiune optimizata a metodei de sortare pentru arborii binari.In cadrul procesului de inserare segventiala a elementelor intr-un arbore definit, sortarea rapida poate concura cu sortarea arborilor binari prin procedeul de sortare prin recursivitate.Algorimul de sortare rapida si cel de sortare a arborilor binar executa un numar egal de comparatii care insa vor avea ordini diferite.

Un alt algoritm de sortate mult mai competitiv cu sortarea rapida este abordat in sortarea prin ansamble (heapsort).Sortaera prin ansamble este oarecum tipica cu sortarea rapida insa este putin mai lenta decat sortarea rapida (quicksort) avant o limita a perioadei de sortare in cazul in care se comporta ineficient definita prin functia O(n logn).Sortarea rapida prezinta de obicei o limita a timpului de sortare foarte buna, putand concura din punct de vedere al performantei cu sortarea prin interclasare, acesta fiind un algoritm din punct de vedere al stabilitatii mult mai stabil decat sortarea rapida sau sortarea prin ansamble si care are un timnp de rulare in cazul in care se comporta ineficient de O(nlogn).Sortarea prin interclasare este adaptata pentru a opera cu liste inlantuite, sau cu liste de mari dimensiuni care sunt stocate in dispozitive de memorare care prezinta un acces foarte lent cum sunt de exemplu CDROM-urile sau bazele de date stocate intr-o retea.Si sortarea rapida poate opera cu listele inlantuite, insa dezavantajul este ca procedura alegerii elemetului pivot poate functiona incet, daca nu se dipaune de un acces aleator la datele care trebuiesc sortate.Principalel dezavantaj al sortarii prin interclasare este este o ineficienta comportare cand se abordeaza structuri de date numite tablouri, necesitand astfel un spatiu de memorie de Ù(n) locatii de memorie cand prezinta o comportare eficienta, comparativ cu sortarea rapida care in aceasta situatie va necesita un spatiu de memorie cu O(log n) locatii.Daca se utilizeaza structuri de date numite liste inlantuite, atunci sortea prin interclasare se comporta mult mai eficient, necesitand un spatiu de memoriec onstant mult mai mic decat in cazul in care aceasta ar trebuie sa sorteze date aflata in tablouri.

7. Analiza principiului de sortare rapida. >>>

Poate ca la definiarea sortarii rapide nu s-a inteles dece algorimul are o perioada de sortare determinata prin functia O(n logn) in cazul in care aceasta se comporta eficient.Sum s-a mentionat in paragrafele de mai sus sortaerea rapida abordeaza principiul inpartirii listelor de date in partitii care contin elemente mai mici sau mai mari decat valoarea elementul pivot.

Daca comportarea este eficienta, atunci de fiecare data cand se formeaza o partitie, lista se imparte in doua parti (sub-liste) egale ca dimensiuni situate foarte aproape una de cealalata, aceasta diun cauza ca numai elementul pivot este "granita" dintre cele doua sub-liste.Prin aceasta se intelege ca ambelor sub-liste li se vor aplica rpocese de sortare recursiva.In cansecinta, va trebui sa se execute un numar de log n aranjari pentru a sorta o lista de dimensiune 1.Prin aceasta se intelege ca adancimea arborelui de aranjament este de O(log n).Insa nu vor exista doau aranjamente (inlocuiri) pentru acelsi nivel de aranjare a proceselor care se exectuta in acceasi parte a listei originale, fiecare nivel al inlocuirilor (aranjamentelor) insumate necesita un timp dat de functia O(n) (fiecare inlocuire are un proces de executie constant, astfel va fi necesar un timp de O(n) pentru ca nivelul sa fie in intregime aranjat (sortat)).Astfel rezulta ca algoritmul sorteaza intreaga lista intr-un timp de O(n logn).

O alta metoda alternativa de sortare este abordarea relatiai de alternare pentru T(n), care reprezinta perioada de timp necesare ca o lista de dimensiune n sa fie in intregime sortata.Deoarece o singura trecere de sortare rapida se executa intr-o perioada de O(n) plus alte doua aranjamente daca lista este partitionata, adica are dimensiunea n/2, atunci relatia poate fi:

T(n)=O(n)+ 2T(n/2)

Relatia aplicata teoremei initiale devine T(n) =È(n logn).

Trebuie sa se intelega ca scopul sortarii rapide nu este de a impartii foarte precis o lista, ca ci se poate intampla ca de fiecare data cand se alege pivotul lista sa se imparta in doua sub-lista: una dintre sub-lista sa contine 99% din elementele listei initiale iar cealalta lista sa contina un procent de numai 1%, iar lista sa aib o adancime de 100log n, astfel intregul proces de sortare se desfasoara intr-un timp de O(n logn).

Iar in cazul in care lista are un comportament ineficient, una dintre cele doua sub-liste vor avea dimensiunea 1 iar cealalata dimensiunea n-1, iar arborele aranjamentelor devine o inalantuire care va contine un numar de naranjamante.Aranjamentul i se va efectua intr-o perioada de timp definita prin relatia O(n - i) rezultand:



Astfel ca relatia devine: T(n) = O(n) + T(1) + T(n-1) = O(n) + T (n- 1),aceasta relatie fiind valabila si pentru sortarea prin insertie si pentru sortarea prin selectie, rezultand astfel ca pana la urma T(n) = È(n²).

8. Analiza complexitatii metodei de sortare. >>>

Majoritatea algoritmilor de sortare detin proprietatea de a realiza o sortare completa intr-un timp de numai O(n logn).Insa scopul principal este alegerea unui element pivot cat mai bun.

Astfel sa presupunem ca terbuie sa se sorteze o lista si ea se imparte in patru parti (partitii).Cele doua partitii aflate la mijlocul listei vor contine cei mai buni pivoti; fiecare dintre acesti pivoti detin valori mai mari in comparatie cu 25% de elemente aflate in lista, si respectiv au valori mai mici comparate cu 25% dintre elementele aflate in lista.Daca nu se reuseste sa se aleaga un pivot intr-un timp constant aflat intre cele doua partitii din mijlocul listei, va trebui ca lista sa se imparte de cel mult 2log²n ori inainte ca lista sa devina o lista de dimnsiune 1 folosindu-ne de un algorit de sortare din familia O(n logn).

9. Analiza sortarii rapide cand aceasta prezinta o complexitate medie. >>>

Daca nu se poate alege intr-o sortare pivoti cu valori diferite, atunci sortarea rapida necesita un timp de numai O(n logn) pentru a realiza toate permutarile (inlocuirile) a alementelor initiale.Insa, deoarece complexitatea medie a sortarii rapide poate insuma perioada de excutie a fiecarei permutari a elementelor listei initiale (intrarii) ea se inparte la n factorial.Procedandu-se astfel , alegerea pivotilor este aleatorie si se poate realiza cu orice tip de algoritm care poate rula ca o noua versiune pentru algoritmul de sortare rapida.

Mai precis, numaru mediu de comparatii efectuate pentru taote inlocuirile (permutarile) segventei de intrare poate fi estimata prin uramtoarea relatie:



In relatia prezentata n-1 reprezinta numarul de comparatii efecuate in partitile in care se face sortarea.Astfel valoarea elementului pivot se poate alege de oriunde in cadrul listei, air suma reprezinta media tuturor partitiilor posibile.

Astfel, se poate ca sortarea rapida poate sa detine o complexitate medie in 39% dintre cazurile in care este abordata, aceasta reprezentand un avantajul pentru care sortarea rapida este unul dintre cei mai preferati algoritmi de sortare.

C(n) = (n-1) + C(n/2) + C(n/2)
C(n) = (n-1) + C(n/2) + C(n/2)
= (n-1) + 2C(n/2)
= (n-1) + 2((n/2) - 1 + 2C(n/4))
= n + n + 4C(n/4) - 1 - 2
= n + n + n + 8C(n/8) - 1 - 2 - 4
= ...
= kn + 2^kC(n/(2^k)) - (1 + 2 + 4 + . . . . . + 2^(k-1))
where log2n > k > 0
= kn + 2^kC(n/(2^k)) - 2^k + 1
-> nlog2n + nC(1) - n + 1.

10. Utilizarea spatiului de memorie. >>>

Spatiul de memorie folosit de catre algoritmul de sortare rapida depinde de versiunea algoritmului utlilizat.

Pentru a aloca un spatiu de memorie sortarea rapida utilizeaza o metoda care are o complexitate de O(log n), care este valabile si in situatia in care algoritmul folosit se comporta ineficient.Insa pentru a ocolii o comportare ineficienta trebie sa sa aiba in vedere urmatoarele aspecte:

* Se utilizeaza metoda partitionarii pe loc.Aceasta neceista O(1) timp de sortare.
* Dupa partitionarea listei initiale va rezulta ca partitia care detine cele mai putine elemente este sortata (prin procedee recursive) prima, necesitand un spatiu de memorie de O(log n) locatii.Astfel daca se incepe sortarea unei alte partitii atunci se va utliza metoda iteratiilor.

Versiunea sortarii rapide care utilizeaza procedura de partitionare pe loc utilizeaza un spatiu de memorie de dimensiune constant chiar si inaintea metodei de recursivitate.Oricum, se executa un numar de O(log n de inlocuiri prin operatii recursive, astfel rezultand ca sortarea rapida trebuie sa memoreze indicii de dimensiuni fixe pentru a furniza informatii referitaore la fiecare termen din lista.Cand algoritmul se comporta eficient vor fi necesare un numar de O(log n) de inlocuiri care vor utiliza un spatiu de memorie de O(log n) locatii.Cand algoritmul se comporta ineficient atunci inlocuirea elementelor sortare se va executa intr-un timp de O(n), necesitand astfel si un spatiu de memorie de O(n) locatii.

Daca se presupune ca se sorteaza arbitrar liste de dimensiuni mari atunci utilizarea unui concept de sortare care sa foloseasca variabile cum ar fi stanga sau dreapta este indicat spre a fi utlizat, deoarece aceste variabile au dimensiuni reduse si nu vor depasii limita constanta a spatiul de memorie alocat la inceputul sortarii; astfel fiind necesare un numar de O(log n) biti pentru a localiza pozitia celor n termeni din lista.Daca se utliziteaza acest concept bazat pe variabilele de stanga si dreapta in fiecare partitie (sub-lista) a listei initiale atunci vor fi necesari un numar de O(log² n) de biti pentru a memora locatiile pozitiilor elementelor din lista in cazul in care algoritmul de sortare se comporta eficient, si in caz contrar vor fi necesari un numar O(n logn).

Daca se foloseste un algoritm de sortare diferite de algoritmul de sortare "pe loc", atunci sortarea rapida va exucuta un numar de O(n) locatii de memorie inainte de a se incepe inlocuirea termenilor.Un astfel de algoritm executa sortarea completa a liste intr-un timp definit pri metoda O(n), deoarece fiecare nivel la care se aplica operatia de recursivitate utilizeaza mai mult spatiu de memorie.Daca elementele listei au dimensiuni diferite atunci rezolvarea devine mai complexa, caci de exemplu daca cele mai multe elemente ale unei liste ce trebuie sortata sunt distincte, atunci pentru a stoca informatii despre acestea este necesar un numar de O(log n) biti, iar numarul de biti necesari pentru a memeora informatii despre aceste elemente va fi necesar un spatiu de memorie de O(n log n) locatii, iar i cazul in care algoritmul care trebuie sa sorteze aceste elemente este ineficient atunci va fi necesar un spatiu de memorie de O(n² log n) locatii.

Structuri de date abstracte | SDA Arbori | SDA Arbori Binari | SDA Arbori Multicai | SDA Arbori Optimi | SDA Graf | Traversarea grafurilor | SDA Graf Ponderat | SDA Graf Orientat | SDA Lista Inlantuita | SDA Tablou Asociat | Despre algoritmi. | Algoritmi de cautare neinformata, cautarea inforamata,cautarea in liste,in grafuri, in SQL-uri | Algoritmi de cautare liniara, binara, interpolare | Prezentare Algoritmi Sortare | Sortare Insertie cu Pas Variabil (Shellsort) | Sortarea Prin Ansamble (Heapsort) | Sortarea Prin Insertie (Insertionsort) | Sortarea Prin Interclasare (Mergesort) | Sortarea Prin Interschimbare (Bubblesort) | Sortarea Prin Selectie (Selectionsort) | Sortarea Rapida (Quicksort)

Inapoi la pagina principala