Laborator 1

1. Sa se determine performanta prin determinarea functiei O() pentru cate o implementare aleasa, a algoritmilor urmatori. a. Bubblesort b. InsertSort 2. Sa se masoare timpii de executie pentru cel putin zece seturi de date de intrare de lungimi diferite pentru functiile reprezentand implementarile algoritmilor precedenti.

1. Sa se determine performanta prin determinarea functiei O() pentu cate o implementare aleasa, a algoritmilor urmatori: a. BubbleSort b. ShakerSort 2. Sa se masoare timpii de executie pentru cel putin zece seturi de date de intrare de lungimi diferite pentru functiile reprezentand implementarile algoritmilor precedenti.

1. Sa se determine performanta prin determinarea functiei O() petru doua implementari diferite ale functiei cmmdc a doua numere (iterativa si recursiva). 2. Sa se compare cele doua variante prin masurarea timpilor de executie pentru cel putin 10 seturi de date de intrare distincte.

#include <iostream> #include <fstream> #include <cstdlib> #include <ctime> #include <string.h>; using namespace std; long length = 1000; const long max_length = 300000; ofstream gout("numere.out"); int a[max_length]; void read() { ifstream fin("numere.in"); for (long i = 0; i < length; i++) { fin>>a[i]; } fin.close(); } void bubbleSort() { int aux; for(long i = 0; i < length; i++) { for(long j = 0; j < length-i-1; j++) { if (a[j] > a[j+1]) { aux = a[j]; a[j]= a[j+1]; a[j+1]= aux; } } } } void insertionSort() { int aux; for(long i = 1; i < length; i++) { aux = a[i]; long j; for(j = i-1; j >= 0 && a[j] > aux; j--) { a[j+1] = a[j]; } a[j+1] = aux; } } void shakerSort() { int i; for(i=0;i<length/2;i++) { int s=0,aux,j; for (j=i;j<length-i-1;j++) { if (a[j]>=a[j+1]) { aux=a[j]; a[j]=a[j+1]; a[j+1]=aux; s=1; } } for (j=length-2-i;j>i;j--) { if(a[j]<=a[j-1]) { aux=a[j]; a[j]=a[j-1]; a[j-1]=aux; s=1; } } if(s==0) break; } } void scrie(char met[]) { gout<<met<<"\t\t:"; for (long i = 0; i < length; i++) { gout<<a[i]<<" "; } gout<<endl; } int euclid(int a,int b) { int r; while(b) { r=a%b; a=b; b=r; } return a; } int cmmdc(int a, int b) { if(b==0) return a; else return cmmdc(b,a%b); } int main() { ofstream fout("timpi.out"); double t1, t2; char met[20]; for (length = 10; length <= max_length; ) { fout << "\nLength\t: " << length << '\n'; gout << "\nLength\t\t\t\t: " << length << '\n'; read(); strcpy(met,"Bubble Sort\t"); t1 = clock(); bubbleSort(); t2 = clock(); scrie(met); fout << "Bubble Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; t1=clock(); euclid(a[length-7],a[length-5]); t2=clock(); cout<<"CMMDC iterativ ("<<a[length-7]<<","<<a[length-5]<<") "<<(t2-t1)/CLK_TCK<<" sec\n"; t1=clock(); cmmdc(a[length-7],a[length-5]); t2=clock(); cout<<"CMMDC recursiv ("<<a[length-7]<<","<<a[length-5]<<") "<<(t2-t1)/CLK_TCK<<" sec\n\n"; read(); t1 = clock(); insertionSort(); t2 = clock(); strcpy(met,"Insertion Sort"); scrie(met); fout << "Insertion Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; read(); t1 = clock(); shakerSort(); t2 = clock(); strcpy(met,"Shaker Sort"); scrie(met); fout << "Shaker Sort\t: " << (t2 - t1)/CLK_TCK << " sec\n"; switch (length) { case 10: length = 50; break; case 50: length = 1000; break; case 1000 : length = 5000; break; case 5000 : length = 10000; break; case 10000 : length = 12000; break; case 12000 : length = 15000; break; case 15000 : length = 50000; break; case 50000 : length = 300001; break; } } fout.close();gout.close(); return 0; }

Fisierul numere.in