Thread: 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;
    }
}