Studiu asupra QuickSort-ului, folosind diferiti pivoti

2

M-am gandit sa ofer o mica idee pentru cei care folosesc tehnica standard de sortare pentru vectori de lungime medie spre ridicat : QuickSort.

Voi aborda 3 situatii,toate 3 bazandu-se doar pe o modalitate diferita de obtinere a pivotului. Mentionez ca in acest articol nu voi sta sa explic implementarea QuickSortului, acest lucru il voi considera ca este stiut de dumneavoastra.Toate cele 3 situatii vor fi exemplificate corect prin ajutorul unei probleme de pe infoarena ce mi-a oferit posibilitatea sa studiez toate cele 3 implementari pentru a vedea care este cea mai eficienta din punct de vedere al vitezei.

Cele 3 situatii sunt urmatoarele :
1. Pivotul reprezinta valoarea medie din intervalul [st,dr] 2. Pivotul reprezinta valoarea din mijlocul intervalului [st,dr] 3. Pivotul reprezinta valoarea aleasa random din intervalul [st,dr]

1. Pivotul reprezinta valoarea medie din intervalul [st,dr]

Pentru a calcula valoarea medie din intervalul [st,dr] evident trebuie calculata suma valorilor din acest interval dupa care sa se faca o normalizare in functie de numarul de valori din vectorul citit.

     mijl = 0;
      for(int i = st; i < = dr; i++)
      mijl+=tablou[i];
      mijl = mijl/(dr-st+1);

Rezultatul acestei "optimizari" este un nefavorabil si incetineste radical rezultatele asupra testului :
Rezultatul optimizarii 1

2. Pivotul reprezinta valoarea din mijlocul intervalului [st,dr]

mijl = tablou[(st+dr)/2];

Aceasta rezolvare ne ofera rezultate imbucuratoare si se observa ca solutia clasica este una din cele mai bune,pana in acest moment.Timpii de executie sunt vizibil imbunatatiti iar TLE`urile lipsesc !
Rezultatul optimizarii 2

3. Pivotul reprezinta valoarea aleasa random din intervalul [st,dr]

Pentru ca toate valorile cuprinse in intervalul [st,dr] sa aiba aceeasi probabilitate de a fi pivotul trebuie ca acesta sa fie ales random.Bineinteles ca in aceasta situatie la fiecare evaluare rezultatele pot fi diferite in bine sau in rau insa in majoritatea situatiilor rezultatele vor fi ceva mai bune. O analiza draguta puteti gasi in "Introducere in algoritmi", de Thomas H. Cormen 😀

mijl = tablou[(int)(st + (std::rand()%(dr-st)))];

Rezultatele sunt putin mai imbunatatatite ca cele de la pivotul la mijloc.Observam o imbunatatire de cateva zecimi pe testele mai mari.
Insa ma repet ca aceste rezultate evaluate de cateva ori pot oferi rezultate mai bune sau mai proaste,datorita faptului ca pivotul nu este tot timpul acelasi.

Rezultatul

Ca o concluzie putem spune ca ultimile doua solutii sunt cele mai bune,ultima dintre acestea oferind rezultatele cele mai bune.Personal folosesc varianta cu pivotul la mijloc prin simplu fapt ca nu exista riscul de a avea o situatie "random" mai nefavorabila.

Cele 3 surse :
Pivot ales folosind media numerelor
Pivot ales la mijlocul intervalului
Pivot ales random

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

Etichete:

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

2 Comentarii

  1. Andrei Misarca spune:
    iulie 14, 2009 la 10:31 pm

    http://www.youtube.com/watch?v=JPyuH4qXLZ0 in una dintre lectii (nu mai stiu exact care) prezinta diverse aspecte ale qsortului. Solutia cu pivotul din mijlocul intervalului poate fi destul de inceata in unele cazuri, de aceea cea mai eficienta este cea cu pivotul random(eficienta consta chiar in acest random).

  2. Avadanei Andrei spune:
    iulie 14, 2009 la 10:54 pm

    Eficienta este data de faptul ca oricare din valorile cuprinse in intervalul [st,dr] are aceeasi probabilitate de a fi un pivot si acest lucru elimina situatiile si problemele ce apar in anumite situatii : vector sortat opus fata de cum avem nevoie,respectiv situatiile cand valorile sunt practic „puse” cu mana 🙂

    Multumesc de completare 🙂