Code:processing in machine wrest case, bast case and so... #include<iostream> #include<ctime> #include<cstdlib> #include<fstream> #define START_SIZE 10000 #define END_SIZE 50000 #define delta 10000 using namespace std; long *data; double time_taken[5][4][500]; //time_taken[i,j,k] the time taken for sorting algorithm i, using data format j, and input size k //i = 0 for insertion, 1 for bubble 2 for selection, 3 for merge sort and 4 for quick sort //j = 0 for ascending, 1 for descending, 2 for random //k refers to the data size 1000 * 10^k void quicksort (long int a[], long int lo, long int hi); void mergeSort(long int A[], long int start, long int end); void merge(long int A[], long int start, long int mid, long int end); void selection_sort(long a[],long n); void bubble_sort(long a[],long n); void insertion_sort(long a[],long n); void set_time_information(long n, int k); void file_findings(int k); int main() { long i,j, n = START_SIZE; int k = 0; while (n <= END_SIZE){ data=new long[n]; set_time_information(n, k); delete [] data; n = n + delta; k++; } file_findings(k); system("PAUSE"); return EXIT_SUCCESS; } void file_findings(int k) { ofstream outf; outf.open("test.txt"); long n = START_SIZE; outf<<"Insertion - Ascending "<<endl; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[0][0][i]<<endl; n = n + delta; } n = START_SIZE; outf<<"Insertion - Descending "<<endl; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[0][1][i]<<endl; n = n + delta; } outf<<"Insertion - Random "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[0][2][i]<<endl; n = n + delta; } outf<<"Bubble - Ascending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[1][0][i]<<endl; n = n + delta; } outf<<"Bubble - Descending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[1][1][i]<<endl; n = n + delta; } outf<<"Bubble - Random "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[1][2][i]<<endl; n = n + delta; } outf<<"Selection - Ascending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[2][0][i]<<endl; n = n + delta; } outf<<"Selection - Descending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[2][1][i]<<endl; n = n + delta; } outf<<"Selection - Random "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[2][2][i]<<endl; n = n + delta; } outf<<"Merge - Ascending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[3][0][i]<<endl; n = n + delta; } outf<<"Merge - Descending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[3][1][i]<<endl; n = n + delta; } outf<<"Merge - Random "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[3][2][i]<<endl; n = n + delta; } outf<<"Quick - Ascending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[4][0][i]<<endl; n = n + delta; } outf<<"Quick - Descending "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[4][1][i]<<endl; n = n + delta; } outf<<"Quick - Random "<<endl; n = START_SIZE; for(int i = 0; i < k; i++){ outf<<n<<"\t"<<time_taken[4][2][i]<<endl; n = n + delta; } outf.close(); } void set_time_information(long n, int k) { cout<<"===============PROCESSING AT SIZE ================="<<n<<endl; long j; clock_t start,end; double time_elapsed; for( j=0;j<=n-1;j++) data[j]=3*j+2; start=clock() ; mergeSort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in ascending order"<<endl; cout<<"\t\tTime analysis of merge sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; quicksort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in ascending order"<<endl; cout<<"\t\tTime analysis of quick sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; insertion_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in ascending order"<<endl; cout<<"\t\tTime analysis of insertion sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock(); bubble_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of bubble sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[1][0][k] = time_elapsed; start=clock(); selection_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of selection sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[2][0][k] = time_elapsed; for(j=0;j<=n-1;j++) data[j]=((4*n)-(3*j+2)); start=clock() ; mergeSort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in Descending order"<<endl; cout<<"\t\tTime analysis of merge sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; quicksort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in Descending order"<<endl; cout<<"\t\tTime analysis of quick sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; insertion_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in Descending order"<<endl; cout<<"\t\tTime analysis of insertion sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][1][k] = time_elapsed; start=clock(); bubble_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of bubble sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[1][1][k] = time_elapsed; start=clock(); selection_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of selection sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[2][1][k] = time_elapsed; for(j=0;j<=n-1;j++) data[j]=(rand()%(3*n)); start=clock() ; mergeSort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in random order"<<endl; cout<<"\t\tTime analysis of merge sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; quicksort(data,0, n-1); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\tData generated in random order"<<endl; cout<<"\t\tTime analysis of quick sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][0][k] = time_elapsed; start=clock() ; insertion_sort(data,n); end=clock(); cout<<"\tData generated in random order"<<endl; cout<<"\t\tTime analysis of insertion sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[0][2][k] = time_elapsed; start=clock(); bubble_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of bubble sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[1][2][k] = time_elapsed; start=clock(); selection_sort(data,n); end=clock(); time_elapsed = double((end-start))/CLOCKS_PER_SEC; cout<<"\t\tTime analysis of selection sort "<<endl; cout<<"\t\t\tStart time "<<start<<"\t end time "<<end<<"\t"; cout<<"Time taken = "<<time_elapsed<<endl; time_taken[2][2][k] = time_elapsed; } void mergeSort(long int A[], long int start, long int end){ long int mid; if (start < end){ mid = (start + end)/2; mergeSort(A, start, mid); mergeSort(A, mid + 1, end); merge(A, start, mid, end); } } void merge(long int A[], long int start, long int mid, long int end){ long int *B = new long int[end-start + 1]; long int i = start, j = mid+1, k = 0; while(i <= mid && j <= end){ if(A[i] < A[j]) B[k++] = A[i++]; else B[k++] = A[j++]; } while(i <= mid)B[k++] = A[i++]; for(long int i=0; i<k; i++) A[start+i] = B[i]; } void quicksort (long int a[], long int lo, long int hi) { // lo & hi are the lower upper indices of the region of array a that is to be sorted long int i=lo, j=hi, h; long int x=a[(lo+hi)/2]; // partition do { while (a[i]<x) i++; while (a[j]>x) j--; if (i<=j) { h=a[i]; a[i]=a[j]; a[j]=h; i++; j--; } } while (i<=j); // recursion if (lo<j) quicksort(a, lo, j); if (i<hi) quicksort(a, i, hi); } void selection_sort(long a[],long n){ long index, temp, i,j; for(j=0;j<n;j++){ index=j; for(i=j+1;i<n-1;i++){ if(a[i]<a[index]) index=i; } temp=a[index]; a[index]=a[j]; a[j]=temp; } } void bubble_sort(long a[],long n){ long i, j, temp; for(i=0;i<n;i++){ for(j=1;j<=n-1-i;j++){ if(a[j-1]>a[j]) { temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } } } void insertion_sort(long a[],long n) { long key,i,j; for(j=1;j<n;j++) { key=a[j]; i=j-1; while(i>=0 && a[i]>key){ a[i+1]=a[i]; i=i-1; } a[i+1]=key; } }