PowerPoint Presentation

SORTAREA RAPIDSORTAREA RAPIDDescrierea sortrii rapideAlgoritmul de sortare rapid, ca i algoritmul de sortare prin interclasare, se bazeaz pe paradigma divide i stpnete.Pentru un subir A[pr] sunt prezentai urmtorii trei pai:Divide: irul A[pr] este mprit n dou subiruri nevide A[pq] i A[q+1r] , astfel nct fiecare element al subirului A[pq] s fie mai mic sau egal dect orice element al subirului A[q+1r] .Stpnete: Cele doua subiruri A[pr] i A[pr] sunt sortate prin apeluri recursive ale algoritmului de sortare rapid.Combin: Deoarece cele dou subiruri sunt sortate pe loc, nu este nevoie de nicio combinare, irul iniial fiind ordonat.Descrierea algoritmului:Quicksort(A,p,r)1: Dac p algoritmul se execut la fel de ncet ca i sortarea prin inserare.

Partiionarea in cazul cel mai defavorabilArbore de recuren cazul cel mai defavorabil . . . ..nPartiionarea in cazul cel mai favorabil Algoritmul lucreaz mult mai repede dac partiionarea produce 2 vectori de n/2 elemente.Formula de recuren este: T(n) = 2 T(n/2) + (n) = (n lg n)Deci dac partiionarea este cea mai bun, atunci produce un algoritm de sortare mult mai rapid.Arbore de recuren cazul cel mai favorabillg nn nnn ( n lg n). . . . . . . .. . . . . . . . . . . . . . . .. . . . .. . . . .. . . . .. . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1nPartiionarea echilibratO mprire in proporie de 9 la 1, pare a fi o partiionare dezechilibrat. n cazul acesta formula recursiv pentru timpul de execuie este: T(n) = T(9n/10) + T(n/10) + n La fiecare nivel al partiionrii are un timp de execuie de (n lg n), adic este la fel ca n cazul partiionrii n 2 pri egale.Deci timpul de execuie este (n lg n) la orice partiionare ntr-o proporie constant.Arbore de recuren pri n proporie de 9 la 1n n n n (n lg n ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 n.. .. .. .. .. .. .. .. .... .. .. .. .. . .. .. .. .. ..Comportarea medieToate permutrile elementelor de intrare sunt la fel de probabile.n situaia n care algoritmul de sortare rapid lucreaz pe o intrare aleatoare, probabil nu va partiiona la fel la fiecare nivel. Unele partiionri vor fi echilibrate, altele nu. Partiionrile bune corespund celui mai bun caz, iar cele rele celui mai defavorabil caz. Variantele aleatoare ale sortrii rapideb)a)O partiionare defavorabil de un cost (n) poate fi absorbit de una bun, tot de un cost (n) i rezult o partiionare favorabil.Timpul de execuie al algoritmului de sortare rapid, cnd partiionrile bune i rele alterneaz, este acelai ca n cazul partiionrilor bune, adic: O(n lg n), doar constanta din notaie O este mai mare.

n concluzie, quick sort-ul este unul dintre cei mai buni algoritmi de sortare.Informatic, grupa 7221algoritmica grafurilor Profesor: ciurea Eleonor Horvat Andreea Istok Andrea

V mulumim!