Finding the time a selection sort takes to sort 100k random numbers

[Robert1234]

I am having trouble getting my program to find the time it takes a selection sort to sort through 100,000 randomly generated items. What have I done wrong? I keep getting a negative number for the time lapsed.

  #include <iostream>
#include <string>
#include <ctime>
#include <array>
using namespace std;

class StopWatch{
 private:
    int startTime;
    int finishTime;
    
 public:
     StopWatch(){
     startTime = 0;
     finishTime = 0;
        
    }
    StopWatch(double t){
     startTime = t;
    }
    
    int start(){
     return startTime;
    }
     
     
    int sort(){
        int data [100000];
        for(int x= 0; x < 100000; x++){
	    data [x] = rand()%98+1;
        }
	int tmp;


	for (int i = 0; i < 100000 -1; i++){

		for (int j = i+1; j < 100000; j++){

			if (data[i] > data[j])
			{
				tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
			}
		}	
	}		
    finishTime = time(0)*1000;
	return finishTime-startTime;	        
    }
        

     
    
};


int main()
{
StopWatch s(time(0)*1000);
cout << "The amount of time it took to sort is " << s.sort()<< " milliseconds" << endl;
}

[liuyang]

If I recall correctly, the time() function does not support milliseconds. By multiplying it with 1000 probably already massed around with the value (possibily already negative number now)

[cire]

The plethora of warnings your compiler emits when compiling this doesn't give you any hints?

warning C4244: '=': conversion from 'time_t' to 'int', possible loss of data

That one, in particular, should not be ignored.

[Robert1234]

@cire My compiler does not give me any warnings. What should I do to fix this though? I am only allowed to use ctime and time(0). Also if I remove the *1000 it returns 0. I still have an issue.

[integralfx]

Why not use std::chrono?
http://www.cplusplus.com/reference/chrono/high_resolution_clock/now/

[Robert1234]

@intergralfx In the book i'm using it says it has to be done using ctime and time(0).

[JLBorges]

> Why not use std::chrono?
> http://www.cplusplus.com/reference/chrono/high_resolution_clock/now/

Two reasons not to use std::chrono::high_resolution_clock
a. std::chrono::high_resolution_clock does not measure processor time.
b. std::chrono::high_resolution_clock may not be monotonic: it can go back in time.

For measuring single-threaded in-memory sort performance, all the clocks in std::chrono are the wrong clocks.
std::time() too is the wrong clock for the same reasons; in addition it typically has a coarse resolution.

To measure the (approximate) processor time, use std::clock()

For more information and links see this thread: http://www.cplusplus.com/forum/beginner/146620/
The last post in the thread has example code: http://www.cplusplus.com/forum/beginner/146620/#msg771618

[Robert1234]

@JLBorgres I am well aware that it is a better way of doing this, but the book tells us to use this explicitly.

[JLBorges]

#include <iostream>
#include <ctime>
#include <chrono>
#include <algorithm>
#include <cstdlib>

struct stop_watch
{
    const std::time_t start_wc_ctime = std::time(nullptr) ;
    const std::chrono::steady_clock::time_point start_sc_chrono = std::chrono::steady_clock::now() ;
    const std::clock_t start_pc = std::clock() ;

    ~stop_watch()
    {
        const auto end_wc_ctime = std::time(nullptr) ;
        const auto end_sc_chrono = std::chrono::steady_clock::now() ;
        const auto end_pc = std::clock() ;

        std::cout << "C wall clock: " << std::difftime( end_wc_ctime, start_wc_ctime ) * 1000 << " milliseconds\n"
                  << "steady clock: " << std::chrono::duration_cast<std::chrono::milliseconds>(
                                                     end_sc_chrono-start_sc_chrono).count() << " milliseconds\n"
                  << "   processor: " << (end_pc-start_pc) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;

    }
};

void selection_sort( int* begin, int* end)
{
    if( begin != end ) 
    {
        std::iter_swap( begin, std::min_element( begin, end ) ); // bring the smallest element to the front
        selection_sort( begin+1, end ) ; // sort the remaining n-1 elements
    }
}

int main()
{
    const std::size_t N = 100'000 ;
    static int array[N] {} ;
    std::generate_n( array, N, std::rand ) ; // deliberately not seeded

    stop_watch sw ;
    selection_sort( array, array+N ) ;
} 

Typical output when there is no contention for processor time:

C wall clock: 5000 milliseconds
steady clock: 4801 milliseconds
   processor: 4790 milliseconds

http://coliru.stacked-crooked.com/a/fdb0af61d6cf6211

[dhayden]

The other suggestions are all valid but I want to address why you're seeing a negative number. The problem is because you're overflowing the precision of a time_t when you multiply by 1000. Time_t is typically a 32 bit signed integer and the current value of "now" is around 1.4 billion.