+skyler_sdf Posted January 24, 2012 Report Posted January 24, 2012 1. Merge-sort //Merge-sort este la fel ca si Quick-sort, o metoda eficienta de sortare. Se procedeaza astfel: //se sorteaza recursiv(crescator) prima jumatate a vectorului, apoi se sorteaza recursiv(crescator) csi a doua jumatate a vectorului. //urmeaza faza de combinare a solutiilor, adica constructia vectorului ordonat pe baza a doi vectori ordonati. //vom construi un alt vector b, vectorul ordonat rezultat din cele doua parti si il vom copia in a, in pozitiile corespunzatoare. #include<iostream.h> #include<conio.h> int a[20],n; //se realizeaza o functie pentru interclasare void interclasare(int i, int m, int j) { int b[20]; //vectorul initial se imparte in doua secvente, aceasta se imparte la randul ei, s.a. pana se ajunge la doua elemente, care se compara //dupa interclasarea celor doua, se executa procesul ptr urmatoarele elemente, s.a. int x=i; int k=1; int y=m+1; while(x<=m && y<=j) if (a[x]<a[y]) b[k++]=a[x++]; else b[k++]=a[y++]; while (x<=m) b[k++]=a[x++]; while (y<=j) b[k++]=a[y++]; int t=i; for (k=1;k<=(j-i)+1;k++) a[t++]=b[k]; } void div_imp(int i, int j) { if (i<j) { int m=(i+j)/2; //se alege mijlocul div_imp(i,m); div_imp(m+1,j); interclasare(i, m, j); } } void main() { cout<<"n="; cin>>n; for(int i=1;i<=n;i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } div_imp(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; getch(); } Pentru a stabili complexitatea algoritmului de sortare prin interclasare, remărcam urmatoarele: - pentru un tablou cu n elemente, numărul de înjumătăţiri succesive până se ajunge la zone de lungime 1 sau 2 este de aproximativ log2n; - la fiecare din aceste divizări succesive, se mută din tab în tab1 şi invers în total n elemente. In consecinta, numarul de operatii elementare executate este de ordinul O(n.log(n)). Mai riguros, daca notam cu C(n) numarul de operaţii elementare pentru sortarea unui tablou cu n componente şi avem în vedere că, la fiecare pas al algoritmului, se fac doua invocări recursive ale metodei de sortare şi o interclasare, iar interclasarea are complexitatea n, atunci C(n) = 2.C(n/2)+n Continuând acest raţionament, putem scrie C(n) = 2(2C(n/4)+n/2)+n = 4C(n/4) + n + n Algoritmul se opreşte după log2(n) astfel de paşi, când se obţine C(n) = nC(n/n) + n + n + ... + n = n.log2(n) In consecinţă, complexitatea algoritmului de sortare prin interclasare este O(n.log2(n)). Constatăm deci că, pentru tablouri cu numar mare de componente, timpul de calcul este mult mai mic în cazul sortării prin interclasare, decât în cazul folosirii algoritmilor simpli, cum ar fi cel al selecţiei, inserţiei sau al bulelor, a căror complexitate este O(n2). Algoritmul de sortare prin interclasare consumă însă de două ori mai multă memorie decât cei simpli mentionaţi, deoarece necesită spaţiu suplimentar pentru tabloul auxiliar . 2. Quicksort //Ordonarea Quick-sort este celebra si una dintre metodele performante de sortare. //Ideea algoritmului este simpla: in vectorul cu capetele inf...sup alegem un element numit pivot si apoi rearanjam elementele vectorului astfel incat in stanga sa se grupeze elemente mai mici sau egale cu pivotul, iar la dreapta elemente mai mari decat pivotul. //in implementare vom alege ca pivot primul element al vectorului, apoi vom folosi doua variabile contor i si j cu care ne deplasam spre dreapta, resp. stanga. //apoi amplasam pivotul pe pozitia dintre cei doi subvectori care se formeaza si apelam quick_sort pentru acestia. //Procesul recursiv se executa doar daca cele doua limite sunt diferite. #include<iostream.h> #include<conio.h> int a[20], n; void quick_sort(int *a, int inf, int sup) //inf si sup sunt capetele vectorului { if(inf<sup) { int pivot=a[inf]; //se alege un pivot, int aux; int i=inf+1, j=sup; //re-aranjam elementele vectorului astfel incat in stanga sa se grupeze elementele mai mici sau egale cu pivotul, iar la dreapta elementele mai mari decat pivotul. //pivotul se alege defapt primul element al vectorului. //cu i si j ne deplasam la dreapta, resp. la stanga. while(i<=j) { while(i<=sup && a[i]<=pivot) i++; while(j>=inf && a[j]>pivot) j--; if(i<j && i<=sup && j>=inf) { aux=a[i]; a[i]=a[j]; a[j]=aux; } } i--; a[inf]=a[i]; a[i]=pivot; //amplasam pivotul pe pozitia dintre cei doi subvectori care se formeaza(unul cu elemente mai mici sau egale, unul cu elemente mai mari) quick_sort(a, inf, i-1); //si apelam quick_sort pentru acestia. quick_sort(a, i+1, pivot); } } void afisare() { int i; cout<<"vectorul sortat este: "; for(i=0; i<n; i++) cout<<a[i]<<" "; } void main() { int i; cout<<"n="; cin>>n; for(i=0; i<n; i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } quick_sort(a, 0, n-1); afisare(); getch(); } Pentru a stabili complexitatea algoritmului Quick Sort aplicată unui tablou cu n componente, notăm cu C(n) numărul de comparaţii efectuate şi remarcăm că, la fiecare pas al algoritmului au loc n comparaţii însoţite de interschimbări ale elementelor şi două invocari recursive ale metodei de sortare, deci C(n) = n + C(k)+C(n-k) unde k este numărul de componente din zona din stânga a tabloului, iar C(k) si C(n-k) sunt complexităţile pentru cele două subzone care urmează a fi sortate recursiv. Situaţia este asemanatoare cu cea întalnită în cazul metodei MergeSort, cu deosebirea că, în acest caz, tabloul nu se mai împarte în două părţi egale. Cazul cel mai favorabil ar fi când, la fiecare recursie, cele două subzone (cu elemente mai mici şi respectiv mai mari decat elementul pivot) ar fi egale. În acest caz, calculul complexităţii se face la fel ca la MergeSort şi deci complexitatea este O(n.log(n)). Cazul cel mai defavorabil ar fi cel în care, la fiecare recursie, elementul pivot ar fi ales în mod atat de nefericit, încat una din cele două subzone obţinute după interschimbări ar fi vida. In acest caz C(n) = n + C(n-1) = n + (n-1) + C(n-2) = ... sau, continuand pana la C(1) C(n) = n + (n-1) + (n-2) + ... + 1 = (n+1)n/2 şi deci complexitatea algoritmului este O(n2). Acest caz "nefericit" este însă foarte puţin probabil. Cel mai probabil este că, în realitate, complexitatea sa fie situată în jurul valorii O(n.log(n)). 3. Heapsort #include<iostream.h> #include<conio.h>. //functia reconstituie_heap: //datele de intrare sunt un vector A si un indice //nodurile stang(i) si drept(i) sunt heap-uri //dar cum elementul A[i] poate fi mai mic decat descendantii sai, este posibil ca acesta sa nu //respecte proprietatea de heap. //aceasta functie face ca subarborele care are radacina in valoarea elementului de indice i, //sa devina heap. void reconstituie_heap(int *A, int i, int dimensiune) { int a, maxim, stang=2*i+1, drept=stang+1; if(stang<dimensiune && A[stang]>A[i]) maxim=stang; else maxim=i; if(drept<dimensiune && A[drept]>A[maxim]) maxim=drept; if(!maxim==i) { a=A[i]; A[i]=A[maxim]; A[maxim]=a; reconstituie_heap(A, maxim, dimensiune); } } //functia construieste_heap: //toate elementele subsirului A[[n/2]+1...n] sunt frunze, ele pot fi considerate heap-uri //formate din cate un element. //functia traverseaza restul elementelor si executa functia reconstituie_heap pentru fiecare nod //intalnit. //ordinea de prelucrare a nodurilor satisface cerinta ca subarborii, avand ca radacina //descendenti ai nodurilor i sa formenze heap-uri inainte ca reconstituie_heap sa fie executat //pentru aceste noduri. void construieste_heap(int *A, int dimensiune) { int i; for(i=(dimensiune-2)/2; i>=0; i--) reconstituie_heap(A, i, dimensiune); } void heapsort(int *A, int dimensiune) { int i, temp; construieste_heap(A, dimensiune); for(i=dimensiune-1; i>=1; i--) { temp=A[i]; A[i]=A[0]; A[0]=temp; dimensiune=dimensiune-1; reconstituie_heap(A, 0, dimensiune); } } void main() { int n, A[50]; cout<<"n="; cin>>n; int i; for(i=0; i<n; i++) { cout<<"A["<<i<<"]="; cin>>A[i]; } heapsort(A,n); cout<<"sirul sortat este: "; for(i=0; i<n; i++) cout<<A[i]<<" "; getch(); } Complexitatea algoritmului este O(nlog(in baza 2)n). 4. Shellsort //Shellsort //Sortarea cu micsorarea incrementului este o extensie simpla al insertion sortului care castiga viteza permitand schimbarea elementelor aflate departe. //Ideea de baza o constituie rearanjarea elementelor din vector in asa fel incat, luand fiecare element (incepand de oriunde), sa obtinem o tabela sortata. //Astfel spunem ca vectorul a este sortat. #include<iostream> using namespace std; int a[1001],n; void shellsort(int a[1001],int n) { int j,i,m,aux; for(m = n/2;m>0;m/=2) { for(j = m;j<=n;j++) { for(i=j-m;i>=0;i-=m) { if(a[i+m]>=a[i]) break; else { aux = a[i]; a[i] = a[i+m]; a[i+m] = aux; cout<<"S-a efectuat o interschimbare : a["<<i<<"] = "<<a[i] <<" cu a["<<i+m<<"] = "<<a[i+m]; cout<<"Starea vectorului este : "; for(int h=1;h<=n;h++) cout<<a[h]<<' '; } } } } } void main () { int i; cout<<"n="; cin>>n; cout<<"\nVectorul Nesortat este: "; for(i=1;i<=n;i++) cin>>a[i]; shellsort(a,n); cout<<"\n\n\nVectorul sortat este: "; for(i=1;i<=n;i++) cout<<a[i]<<" "; } Complexitatea algoritmului: 1. Cazul cel mai favorabil când vectorul e sortat crescǎtor: omega(n); 2. Cazul cel mai nefavorabil când vectorul e sortat descrescǎtor: O(n2). 5. Selective sort Acest algoritm selecteaza la fiecare pas i cel mai mic element din vectorul de la pasul i+1 pana la n. Valoarea minima de la pasul i este pusa in vector la pozitia i, facandu-se interschimbarea cu vectorii mari; in majoritatea cazurilor oferind rezultate mai slabe decat insertion sort. void selective(int a[],int n) { int i,aux,min,minat; for(i = 0; i < n - 1;i++) { minat = i; min = a[i]; for(j = i + 1;j < n;j++) //selectam minimul din vectorul ramas( de la i+1 la n) { if(min > a[j]) //sortare crescatoare { minat = j; //pozitia elementului minim min = a[j]; } } aux = a[i] ; a[i] = a[minat]; //interschimbare a[minat] = aux; } } 6. Insertion sort Sortarea prin insertie seamana oarecum cu sortarea prin selectie. Tabloul este impartit imaginar in doua parti - o parte sortata si o parte nesortata. La inceput, partea sortata contine primul element al tabloului si partea nesortata contine restul tabloului. La fiecare pas, algoritmul ia primul element din partea nesortata si il insereaza in locul potrivit al partii sortate. Cand partea nesortata nu mai are nici un element, algoritmul se opreste. void insertion(int a[], int n) { int i, j, aux; for (i = 1; i < n; i++) { j = i; while (j > 0 && a[j - 1] > a[j]) { aux = a[j]; a[j] = a[j - 1]; a[j - 1] = aux; j--; } } }
deli Posted August 3, 2013 Report Posted August 3, 2013 metoda quicksort are o eroare de sintaxa : in loc de quick_sort(a, i+1, pivot); ar trebui quick_sort(a, i+1, sup);
Recommended Posts
Please sign in to comment
You will be able to leave a comment after signing in
Sign In Now