sorting algorithm repeating a test

[rwill357]

I was wondering if there were away to repeat the same test multiple times and average the time.

The code works fine

#include <cstdlib> 
#include <ctime> 
#include <iostream>

using namespace std;
 
void PrintArray(int* array, int n); 
void QuickSort(int* array, int start, int end); 
int partition(int* array, int pivot, int start, int end); 
void swap(int &temp, int &tmp2); 
double diffclock(clock_t clock1,clock_t clock2) 
{ 
 double diffticks=clock1-clock2; 
 double diffms=(diffticks*10)/CLOCKS_PER_SEC; 
 return diffms; 
} 

 
int main(void) 
{ 
            int ARRAY_SIZE;
			cout<< "How many random numbers would you like generated? " << endl;
			cin >> ARRAY_SIZE;

		int* array = new int[ARRAY_SIZE]; 
 
		srand((unsigned)time(0)); 
     
		for(int i=0; i<ARRAY_SIZE; i++){ 
        array[i] = (rand()%100000)+1; 
        }
         
        PrintArray(array, ARRAY_SIZE); 
		clock_t begin=clock(); 
        QuickSort(array,0,ARRAY_SIZE - 1);                               
        cout<<endl<<"The list has been sorted, now it is : "<<endl; 
        PrintArray(array, ARRAY_SIZE); 
		clock_t end=clock(); 
		cout<<"Execution time: "<<diffclock(end,begin)<<" ms."<<endl; 
        		
		cin.get(); 
        cin.get(); 
		system("PAUSE");
		delete[] array;

        return 0; 
} 
 
void swap(int &temp, int &tmp2) 
{ 
        int tmp; 
        tmp = temp; 
        temp = tmp2; 
        tmp2 = tmp; 
} 

void PrintArray(int* array, int n) 
{ 
        int i; 
          
        for( i = 0; i < n; i++) cout<<array[i]<<'\t'; 
} 
  
void QuickSort(int* array, int start, int end) 
{ 
        int pivot = array[start];                                  
        int middle; 
         
        if(start < end)                                                
                                                                                                           
                                                                                                           
        { 
                middle = partition(array, pivot, start, end); 
                                                                                                          
                                                                                                           
                array[middle] = pivot; 
                QuickSort(array, start, middle-1);    
                QuickSort(array, middle+1, end);         
        } 
} 
 
int partition(int* array, int pivot, int start, int end) 
{ 
        int leftLimit = start; 
        int rightLimit = end; 
         
        while(leftLimit < rightLimit)                         
        { 
                 while( pivot < array[rightLimit]               
                                && rightLimit > leftLimit)          
                 { 
                          rightLimit--;                                               
                 } 
                 swap(array[leftLimit], array[rightLimit]); 
                                         
                  
                 while( pivot >= array[leftLimit]             
                                && leftLimit < rightLimit)           
                 { 
                          leftLimit++;                               
                 } 
                 swap(array[rightLimit], array[leftLimit]); 
                                  
        } 
        return leftLimit;                                            
                                                                                                                                                               //leftBoundary and rightBoundary are equal 
}

[Krstevski]

You can not determine the time of execution because the program runs on RAM and the run-time will be different on other computer.
You can determine only the complexity of algorithms...

The Insertion Sort is the best algorithm for sorting...

void InsertionSort(int A[], int n){
    int j, i, pom;
    for(i=1; i<n; i++){
        pom=A[i];
        for(j=i; j>0 && A[j-1]>pom; j--)
              A[j]=A[j-1];
        A[j]=pom;
    }
}

Avarage time:
[img]http://img402.imageshack.us/img402/5803/alg.jpg[/img]

[rwill357]

Thank you for answering so quickly. I know that I should be concerned with complexity but I calculate and average 5 test in ms and display the output

[dusktreader]

You can not determine the time of execution

You can determine the time of execution. While the time is dependant on system load and hardware, you can still get an idea of performance using timing methods. After all, that's what they do in the industry to compare software. The easiest method is probably to use the clock() function that is part of <ctime> ( or <time.h> ) int the standard template library. Note that you will need to use the CLOCKS_PER_SEC macro to convert the value from clock ticks to seconds ( expressed as a double if you do it right ).

The Insertion Sort is the best algorithm for sorting...

Dead wrong. Insertion sort is great with very small lists, but not so good with large lists. It's best case performance is O(n) which seems nice, but this will hardly ever happen with real data. Instead, you are much more likely to get the average and worst case performance of O(n^2). Usually, for simple implementations, quicksort or mergesort are two of the better performers.

[Krstevski]

Wait... You want to display average run-time time of the program who is tested on the 5 test cases ?

If you want that... here is the algorithms to get run-time of the program:

#include <time.h>
#include <iostream>

using namespace std;

int main() {
	int clo = clock(); // Start Timer
        // Do something here...

        // e.g:
	int a = 0;
	for(int i=0; i<90000; i++) {
		for(int j=0; j<5000; j++) {
			a+=a;
		}
	}

        // Print run-time in ms
	cout << (clock() - clo) << endl;
	cin.get();
}

NOTE: Run-time of the program will be different on other computer.

Implement this algorithm in your program and get the run-time :)

But if you requested something else, tell me and we will try to help you.

Edit: @dusktreader, I know about this, but as I said "other computer = other run-time".
For sorting algorithms... hmm, I`m not sure, but I will see about your suggest, thanks. :)

[niknailer]

I played with your code some to get the average of if I ran it 5 times using the following code. I also took out the PrintArray lines in the main. It works fine for smaller numbers like 100 but when I put in larger numbers such as 100000, it runs once and then stops. Not sure why it is doing it but if you are only going to have smaller numbers to input then this could work.

int main() 
{ 
            int ARRAY_SIZE;
			double tm;
			double tim = 0;
			double avg;
			cout<< "How many random numbers would you like generated? " << endl;
			cin >> ARRAY_SIZE;

		int* array = new int[ARRAY_SIZE]; 
 
		srand((unsigned)time(0)); 
     
		for(int i=0; i<ARRAY_SIZE; i++){ 
        array[i] = (rand()%100000)+1; 
        }
		for(int c=0; c<5; c++){
         
		clock_t begin=clock(); 
		 
        QuickSort(array,0,ARRAY_SIZE - 1);                               
        cout<<endl<<"The list has been sorted, now it is : "<<endl; 
          
		clock_t end=clock(); 
		tm=diffclock(end,begin);
		cout<<"Execution time: "<< diffclock(end,begin) <<" ms."<<endl; 
		tm=diffclock(end,begin);
		tim = tm + tim;
		
		}		
		avg= tim/5;
		cout << "Average time: "<< avg <<endl;

		cin.get;

		delete[] array;
		

        return 0; 
}