Page 38 - MATINF Nr. 7

38 C. B˘alc˘au

ˆ
Observat ,ia 4. In ˆıncercarea de a evita cazurile devavorabile ale algoritmului de sortare rapid˘a,
s-au propus variante ale algoritmului ˆın care se urm˘ares , te o echilibrare a celor dou˘a partit , ii.
De exemplu, o variant˘a const˘a ˆın alegerea drept pivot a elementului din mijloc din ordonarea
cresc˘atoare a trei elemente: elementele de la cele dou˘a margini (a p s , i a u ) s , i elementul median (a m ,
p + u
j k
m = ), variant˘a numit˘a metoda medianei din trei (median-of-three quicksort).
2
Mai multe detalii privind implementarea s , i complexitatea acestei variante, precum s , i a altor
variante ale algoritmului de sortare rapid˘a, pot fi g˘asite ˆın [9] s , i [10].

Bibliografie

[1] Gh. Barbu, I. V˘aduva, M. Bolos , teanu, Bazele informaticii, Editura Tehnic˘a, Bucures , ti, 1997.

[2] C. B˘alc˘au, Optimalitatea algoritmului de c˘autare binar˘a, MATINF I (2018), nr. 1, 39–51.
[3] C. B˘alc˘au, Complexitatea algoritmilor de sortare, MATINF II (2019), nr. 3, 41–48.

[4] C. B˘alc˘au, Complexitatea algoritmului de sortare prin interclasare (mergesort), MATINF III
(2020), nr. 5, 15–24.

[5] A. Carabineanu, Structuri de date, http://ebooks.unibuc.ro/informatica/carabineanu/CARA_
STR.pdf.

[6] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press,
Cambridge, 2009.

[7] H. Georgescu, Tehnici de programare, Editura Universit˘at , ii din Bucures , ti, Bucures , ti, 2005.

[8] D.E. Knuth, The Art Of Computer Programming. Vol. 3: Sorting and Searching, Addison-
Wesley, Reading, MA, 1998.

[9] R. Sedgewick, P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley,
New Jersey, 2013.

[10] R. Sedgewick, K. Wayne, Algorithms, Addison-Wesley, Massachusetts, 2011.