what is ALGORITHM this implementation an sorting and ascending order.
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;
}
}