Thread: what is ALGORITHM this implementation an sorting and ascending order.

  1. #1
    Registered User
    Join Date
    Dec 2012
    Posts
    3

    Post 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;
        }
    }
    Last edited by ermias1love; 12-26-2012 at 04:26 AM.

  2. #2
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    428
    Welcome to the Board! ;o)

    Your question does not translate into english well. Maybe a more detailed description of what you are trying to accomplish would help and any compiler errors you may be getting.

    I can say that your indentation in int main is quite sloppy. Maybe clean it up a little?
    Virtual reality hello world http://www.rodneybrothers.com/vr/vrh...rld/index.html in html and javascript.
    Viewable with dodocase, google cardboard, OR, and other compatible VR gear.

  3. #3
    Registered User
    Join Date
    Dec 2012
    Posts
    3
    I need to how to analysis to algorithms to determine the amount of resources (such as time and storage) necessary to execute it.


  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    For storage, it's how many items is space allocated for with new[], plus how deep does the recursion go.
    For time, a common measure is the number of comparisons between items.

    Do you need worst-case answers, or average case, or both?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Dec 2012
    Posts
    45
    Quote Originally Posted by iMalc View Post
    [..]For time, a common measure is the number of comparisons between items.[..]
    I would add the number of copy operations. A careful implementation of insertion sort, for example, requires only O(n log n) comparisons. (You can use a binary search to determine the insertion point)

  6. #6
    Registered User
    Join Date
    Dec 2012
    Posts
    3
    @iMalc yes please, both of worst-case and average case.
    how to define on algorithm or write to report?
    Last edited by ermias1love; 12-27-2012 at 05:05 AM.

  7. #7
    Registered User
    Join Date
    Dec 2012
    Posts
    45
    I still don't understand which is your question. The program you posted seems to do exactly that: test some sorting algorithms with different data sets (shuffled / sorted / reverse-sorted) of different sizes, measure the time they take, and print the result.

    All you have to do is run the program and see, for every algorithm, how does the time change when the size is increased.

    By the way, where is the 'delete' for that 'new' in function merge()?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting dates into ascending order
    By DarkEmpire in forum C Programming
    Replies: 2
    Last Post: 03-06-2012, 11:01 AM
  2. Replies: 9
    Last Post: 04-01-2011, 04:13 PM
  3. Ascending Numerical Order
    By Yizi in forum C Programming
    Replies: 7
    Last Post: 12-08-2009, 07:05 PM
  4. 3 integers in ascending order
    By hobilla in forum C Programming
    Replies: 7
    Last Post: 02-14-2009, 01:01 PM
  5. sorting arrays (ascending order)
    By utoots in forum C++ Programming
    Replies: 3
    Last Post: 04-08-2003, 08:57 AM

Tags for this Thread