I am trying to time the execution of a quicksort algorithm in C++ but for some reason it constantly returns 0 for me, which clearly can't be right!
I don't know where I am gooing wrong, so any help would be greatly appreciated!I have the code done for arrays of size 10,50,100,500 and 1000 but since the code is similart for them all I will just give the code for the arrays of size 10 and 50.

#include <iostream>
#include <time.h>
#include <cstdlib>
using namespace std;

void quickSort(int arr[],int left,int right) { /*This is the quickSort function that will sort all of the elements in an array in ascending order*/
    int i=left,j=right;
    int tmp;
    int pivot = arr[(left + right) / 2];
    /* partition */
    while (i <= j) {
        while (arr[i] < pivot)
        i++;
        while (arr[j] > pivot)
        j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        };
        /* recursion */
        if (left < j)
            quickSort(arr, left, j);

        if (i < right)
            quickSort(arr, i, right);
}

void time(int arr[],int left,int right){
    clock_t stopwatch,t1,t2;    /*These 3 lines are timing the exection of the quicksort to take place*/
    t1=clock();
    quickSort(arr,left,right);
    t2=clock();     /*Used to time the quicksort*/
    cout<<"t1 = "<<t1<<endl;
    cout<<"t2 = "<<t2<<endl;
    stopwatch=t2-t1;        /*How long it took to execute the quicksort*/
    cout<< "Stopwatch ="<<stopwatch<<endl;    /*Displaying how long it took to execute the code-i.e.how long the quickSort function took*/

}

int main()
{
    int arraya[10],arrayb[50],i;

    srand(time(NULL));      /*Seed for a random number generator*/
    for(i=0;i<10;i++)
    arraya[i]=rand();
    time(arraya,0,9);  
    cout<<"The sorted array of 10 elements is :\n";
    for(i=0;i<10;i++){      
    cout<<"arraya ["<<i<<"] = "<<arraya[i]<<"\n";}

    srand(time(NULL));          for(i=0;i<50;i++)
    arrayb[i]=rand();
    time(arrayb,0,49);   
    cout<<"The sorted array of 50 elements is :\n";
    for(i=0;i<50;i++){      
    cout<<"arrayb ["<<i<<"] = "<<arrayb[i]<<"\n";}
    return 0;
}

Thanks in advance.

Recommended Answers

All 6 Replies

I'm sure people will come up with other methods that are better (or better suited for the situation), but look at http://cplus.about.com/od/howtodothingsi2/a/timing.htm at least for a reference as to some of the issues, and perhaps how to get a little more resolution out of the timer, YMMV.

One thing that will help for sure is to run your algorithm through multiple times and get the total time and divide by the number of passes to get an average.

I've been playing around with it for hours but it just isn't working.....

Did you try the method that was outlined in the blog post? I can't recall the resolution for the functions in time.h, but it's pretty coarse.

Test what you have with something that is known (wrap your timing around a bunch of math functions in a loop and repeat them thousands of times) and see if you can register anything.

What platform (OS + version) and compiler (type and version) are you using?

Hello digitup1,
It gives zero because the time taken to do quicksort function is so small. To test that your time function works right use some loops in your code to make time delay. For example like this...

long int c;
for(c=1;c<=100000;c++)
{cout<<" ";
}

Instead of timing how long it takes to run qsort sort once, execute qsort n times in a loop and see how long that takes. Vary n, until you get a reasonalble time.


// startTime;

for (size_t i=0 i < 100000; i++ )
{
qsort();
}

// endTime

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.