4 Replies - 1414 Views - Last Post: 11 December 2012 - 03:41 PM Rate Topic: -----

#1 captjackAV  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 captjackAV  Icon User is offline

  • New D.I.C Head

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

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 12:16 PM

View Postipushmycar, 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.
Was This Post Helpful? 0
  • +
  • -

#4 ipushmycar  Icon User is offline

  • D.I.C Regular

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

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 12:22 PM

Glad you got it working.
Was This Post Helpful? 0
  • +
  • -

#5 Adak  Icon User is offline

  • D.I.C Lover
  • member icon

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

Re: Finding time it takes to quicksort a list

Posted 11 December 2012 - 03:41 PM

View PostcaptjackAV, on 11 December 2012 - 12:16 PM, said:

View Postipushmycar, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1