Algoritmica - Curs

[nighthawk]

Am si eu niste cursuri de algoritmica de la facultate. Poate is utile cuiva. Pt mina au fost

http://web.info.uvt.ro/~dzaharie/

*nu cred ca are si quick sort, nui la nivelul ala, dar nah pt incepatori e OK

**mai is ceva cursuri pe akolo pe site.

Desi daca e sa invetzi algoritmi mai bene citesti Donald Knuth ( numa ca nu e in romana ). Se gasesc pe torrente toate 3 volume.

[zbeng]

METODA QUICK SORT

Metoda Quick Sort faca parte din clasa metodelor avansate de

sortare si s-a dovedit ca este cea mai rapida metoda de

sortare bazata pe interschimbarea elementelor.

Aceasta metoda se recomanda a se folosi in special in cazul

sirurilor care sunt foarte "amestecate" (sir cvasi aleator).

In acest caz se poate observa in mod special superioritatea

metodei QuickSort.

Algoritmul in pseudocod este:

QuickSort(inceput,sfarsit)

i=inceput

j=sfarsit

temp=a[(i+j)/2]

repeta

cat timp a<temp executa

i=i+1

sf cat timp

cat timp a[j]>temp executa

j=j-1

sf cat timp

daca i<j atunci

schimba a,a[j]

sf daca

daca i<=j atunci

j=j-1

i=i+1

sf daca

pana cand i>=j

daca inceput<j atunci

QuickSort(inceput,j)

sf daca

daca i<ultimul atunci

QuickSort(i,ultimul)

sf daca

Ideea acestei metode de sortare este aceea de a alege un pivot si

a-l pozitiona pe acesta pe locul corespunzator conform ordinii. Odata

acel element fixat se realizeaza acelasi lucru si pentru subsirurile

din partea dreapta si stanga.

Complexitatea este de O(n*ln(n)) in mediu desi poate ajunge si

la O(n^2).