O.I.A.M.• Coordonator : Muresan Octavia• Incarcarea fisierului pe pagina wiki si

personalizarea paginii: Muresan Octavia• Editare documente si ppt: Andrei Iulia• Grafica ppt si pagina wiki: Andrei Iulia• Documentarea si conceperea machetei ppt:

Hatos Alexandra

Un programator

If trei versuri se declamăAnd un vers un pic obscen

Then făcuşi o epigramăElse făcuşi doar un catren.

epigramă de Dan Norea

În practicã algoritmul de sortare cel mai rapid este Quicksort numitã sortare rapidã, care foloseste partitionarea ca idee de bazã. Este mai rapidã decât orice metodã de sortare simplã, se executã bine pentru fisiere sau tabele mari, dar ineficient pentru cele mici.Strategia de bazã folositã este "divide et impera", pentru cã este mai usor de sortat douã tabele mici, decât una mare. Algoritmul este usor de implementat, lucreazã destul de bine în diferite situatii si consumã mai putine resurse decât orice altã metodã de sortare în multe situatii. Necesitã numai în jur de NlogN operati în cazul general pentru a sorta N elemente.

Metoda QuickSort presupune gasirea pozitiei finale pe care o ocupa elemenetul de pe prima pozitie comparandu-l cu elementele din cealalta partitie a tabelului, acest algoritm realizandu-se pana cand partitia are 1 element.

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.

• 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.

Problema :• Fie vectorul a cu n componente numere intregi (sau

reale). Se cere ca vectorul sa fie sortat crescator.Rezolvare :Este necesara o functie poz care trateaza o portiune din vector, cuprinsa intre indicii dati de li (limita inferioara) si ls (limita superioara). Rolul acestei functii este de a pozitiona prima componenta a [li] pe o pozitie k cuprinsa intre li si ls, astfel incat toate componentele vectorului cuprinse intre li si k-1 sa fie mai mici sau egale decat a[k] si toate componentele vectorului cuprinse intre k+1 si ls sa fie mai mari sau egale decat a[k].

In aceasta functie exista doua moduri de lucru:a) i ramane constant; j scade cu 1;b) i creste cu 1; j ramane constant.

Functia este conceputa astfel:• Initial, i va lua valoarea li, iar j va lua valoarea ls

(elementul care initial se afla pe pozitia li se va gasi mereu pe o pozitie data de I sau de j);

• Se trece in modul de lucru a);• Atat timp cat i<j , se executa:

- daca a[i] este strict mai mare decat a[j], atunci se inverseaza cele doua numere si se schimba modul de lucru;

- i si j se modifica corespunzator modului de lucru in care se afla programul;

- k ia valoarea comuna a lui i si j. Functia QUICK are parametrii li si ls (limita

inferioara si limita superioara). In cadrul ei se utilizeaza metoda DIVIDE ET IMPERA, dupa cum urmeaza:• se apeleaza POZ;• se apeleaza QUICK pentru li si k-1;• se apeleaza QUICK pentru k+1 si ls.

type vector=array [1..100] of integer;var i,n,k:integer; a:vector,

procedure poz (li,ls:integer; var k:integer; var a:vector);

Var i,j,c,i1,j1:integer;Begin i1:=0; j1:=-1; i:=li; j:=ls;While i<j do begin if a[i]>a[j] then begin

c:=a[j]; a[j]:=a[i]; a[i]:=c;

c:=i1; i1:=-j1; j1:=-cend;

i:=i+i1; j:=j+j1 end;k:=Iend;

procedure quick (li,ls:integer);begin if li<ls then begin poz(li,ls,k,a); quick(li,k-1); quik(k+1,ls) endend;

begin write(`n=`); readln(n); for i:=1 to n do begin write(`a[`,I,`]=`); readln(a[i]) end; quick(1,n); for i:=1 to n do writeln (a[i])end.