Finding time it takes to quicksort a list

Page 1 of 1

4 Replies - 2110 Views - Last Post: 11 December 2012 - 03:41 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=303623&amp;s=e52dc216f663cb0f5b723e2a57869877&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 captjackAV

Reputation: 0
• Posts: 15
• Joined: 24-April 12

Finding time it takes to quicksort a list

Posted 11 December 2012 - 11:59 AM

My program lets the user input a list of numbers and quicksorts the list. I print the list before and after it is quicksorted. That part is working fine. My problem is displaying how long it took to do the quicksort. When I do it, it always says 0.00 sec. I assume this is because it is sorted so fast. So I tried to write a program where I sort the list like 1000 times so that I can find the actual time it took to sort the list. Below is my code. I was wondering if you could help me fix it by giving me that portion of the code. I understand what to do, but I just can't seem to make it work.

Thank You!

```#include <iostream>
#include "ArrayListType.h"
#include <stdio.h>
#include <time.h>
#include <ctime>

using namespace std;

int main()
{
arrayListType<int> intList2;
time_t start, end;
double timedif;
const int runs = 1000000;
int num;

//quickSort

cout<<"Enter numbers ending with 007"<<endl;
cin>>num;

while(num != 007)
{
intList2.insert(num);
cin>>num;
}

cout << "The list before sorting:" ;
intList2.print();
cout << endl << endl;

[b]time(&start);
for(int r=0; r < runs; ++r)
{
intList2.quickSort();
}
time(&end);

timedif = difftime(end,start);
double realduration = timedif/(double)runs;

cout << "The list after quicksort: " ;
intList2.print();
printf("It took you %.0001f seconds to sort the list.\n ", realduration);[/b]

```

Is This A Good Question/Topic? 0

Replies To: Finding time it takes to quicksort a list

#2 ipushmycar

• D.I.C Regular

Reputation: 86
• Posts: 390
• Joined: 29-August 10

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 12:03 PM

http://www.cplusplus...ce/ctime/clock/

shows a good example of them timing a function.

#3 captjackAV

Reputation: 0
• Posts: 15
• Joined: 24-April 12

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 12:16 PM

ipushmycar, on 11 December 2012 - 12:03 PM, said:

http://www.cplusplus...ce/ctime/clock/

shows a good example of them timing a function.

Thank You! I implemented that and here was my output

Enter numbers ending with 007
1 23 789 456 2 82 98 65 32 72 93437 37976 8976 8 007
The list before sorting:1 23 789 456 2 82 98 65 32 72 93437 37976 8976 8

The list after quicksort: 1 2 8 23 32 65 72 82 98 456 789 8976 37976 93437
It took you 0.670000 seconds to sort the list

I believe it makes logical sense.

#4 ipushmycar

• D.I.C Regular

Reputation: 86
• Posts: 390
• Joined: 29-August 10

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 12:22 PM

• D.I.C Lover

Reputation: 331
• Posts: 1,168
• Joined: 01-April 11

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 03:41 PM

captjackAV, on 11 December 2012 - 12:16 PM, said:

ipushmycar, on 11 December 2012 - 12:03 PM, said:

http://www.cplusplus...ce/ctime/clock/

shows a good example of them timing a function.

Thank You! I implemented that and here was my output

Enter numbers ending with 007
1 23 789 456 2 82 98 65 32 72 93437 37976 8976 8 007
The list before sorting:1 23 789 456 2 82 98 65 32 72 93437 37976 8976 8

The list after quicksort: 1 2 8 23 32 65 72 82 98 456 789 8976 37976 93437
It took you 0.670000 seconds to sort the list

I believe it makes logical sense.

Quicksort is sorting 14 integers in 0.67 seconds?

That's alarmingly slow! Are you sorting on a cell phone?

I'm not familiar with C++ but using C and an array of integers (in any order, even already sorted order), I see 100,000 integers being sorted in less time, with Quicksort.

Is this "list" a linked list perhaps? That would make some sense.