Keep getting 0 seconds for each sorting algorithm?

[Lacy9265]

For this program I have to time selection, bubble, insertion, merge, quick and radix sort by using <ctime>. When the program runs it should tell you how long it took to sort the array and the array sorted Every time I run the program the time for each sort is 0 seconds. Could someone tell why I keep getting 0 seconds for each sort. The program includes driver.cpp, driver.h, and sorting.cpp. However my files are too big for one post. So I have only included the driver.cpp. Where I'm actually timing each sort.

#include "Driver.h"
#include <stdio.h>
#include <ctime>
#include <iostream>



int main()
{
    // Declare variables 
    int array[] = { 42, 4, 5, 600, 1200, 75, 21, 18, 1, 99}; // Array that holds the numbers 
    int array_size = sizeof(array) / sizeof(array[0]); // The size of the array 
    double doneTime;
    
// ---------------------------------------------------------------------------------------------------------------------
    // Selection Sort
    // See how long it takes for the array to be sorted 
    clock_t start = clock(); // Start the clock
    selectionSort(array, array_size); 
    clock_t finish = clock(); // Stop the clock after sort is finished 
    doneTime = static_cast<double>(finish - start) / CLOCKS_PER_SEC; // Calculate how long it took to sort the array
    std::cout << "The time it took to store the array for selection sort: "; // Message on how long it took
    std:: cout << doneTime << " seconds\n";  // Print out how long it took
    // Show the array after it has been sorted
    std::cout << "Array Sorted (selection sort):\n";
    printArray(array, array_size);  // Call on the printArray function
// ----------------------------------------------------------------------------------------------------------------------

    // Bubble Sort
    // See how long it takes for the array to be sorted 
    clock_t start_bubble = clock(); // Start the clock
    bubbleSort(array, array_size); 
    clock_t finish_bubble = clock(); // Stop the clock after sort is finished 
    doneTime = static_cast<double>(finish_bubble - start_bubble) / CLOCKS_PER_SEC; // Calculate how long it took to sort the array
    std::cout << "\n\nThe time it took to store the array for bubble sort: "; // Message on how long it took
    std::cout << doneTime << " seconds\n";  // Print out how long it took
    // Show the array after it has been sorted
    std::cout << "Array Sorted (bubble sort):\n";
    printArray(array, array_size);  // Call on the printArray function
// -----------------------------------------------------------------------------------------------------------------------



// ----------------------------------------------------------------------------------------------------------------------
    // Insertion Sort
    // See how long it takes for the array to be sorted 
    clock_t start_insertion = clock(); // Start the clock
    insertionSort(array, array_size); 
    clock_t finish_insertion = clock(); // Stop the clock after sort is finished 
    doneTime = static_cast<double>(finish_insertion - start_insertion) / CLOCKS_PER_SEC; // Calculate how long it took to sort the array
    std::cout << "\n\nThe time it took to store the array for insertion sort: "; // Message on how long it took
    std::cout << doneTime << " seconds\n";  // Print out how long it took
    // Show the array after it has been sorted
    std::cout << "Array Sorted (insertion sort):\n";
    printArray(array, array_size);  // Call on the printArray function
// -----------------------------------------------------------------------------------------------------------------------




// ------------------------------------------------------------------------------------------------------------------
     // Merge Sort
    // See how long it takes for the array to be sorted 
    clock_t start_merge = clock();
    mergeSort(array, 0, array_size - 1);
    clock_t finish_merge = clock();
    doneTime = static_cast<double>(finish_merge - start_merge) / CLOCKS_PER_SEC;
    std::cout << "\n\nThe time it took to store the array for merge sort: ";
    std::cout << doneTime << " seconds\n";
    // Show the array after it has been sorted
    std::cout << "Array Sorted (merge sort):\n";
    printArray(array, array_size);
// --------------------------------------------------------------------------------------------------------------------



 // ----------------------------------------------------------------------------------------------------------------------
    // Quick Sort
    // See how long it takes for the array to be sorted 
    clock_t start_quick = clock(); // Start the clock
    quickSort(array, 0, array_size - 1);
    clock_t finish_quick = clock(); // Stop the clock after sort is finished 
    doneTime = static_cast<double>(finish_quick - start_quick) / CLOCKS_PER_SEC; // Calculate how long it took to sort the array
    std::cout << "\n\nThe time it took to store the array for quick sort: "; // Message on how long it took
    std::cout << doneTime << " seconds\n";  // Print out how long it took
    // Show the array after it has been sorted
    std::cout << "Array Sorted (quick sort):\n";
    printArray(array, array_size);  // Call on the printArray function

 // -----------------------------------------------------------------------------------------------------------------------  

 
 
 
 // ----------------------------------------------------------------------------------------------------------------------
    // Radix Sort
    // See how long it takes for the array to be sorted 
    clock_t start_radix = clock(); // Start the clock
    radixSort(array, array_size);
    clock_t finish_radix = clock(); // Stop the clock after sort is finished 
    doneTime = static_cast<double>(finish_radix - start_radix) / CLOCKS_PER_SEC; // Calculate how long it took to sort the array
    std::cout << "\n\nThe time it took to store the array for radix sort: "; // Message on how long it took
    std::cout << doneTime << " seconds\n";  // Print out how long it took
    // Show the array after it has been sorted
    std::cout << "Array Sorted (radix sort):\n";
    printArray(array, array_size);  // Call on the printArray function
// -----------------------------------------------------------------------------------------------------------------------  
    

[seeplus]

Use a Timer class (from http://www.cplusplus.com/forum/beginner/278466/3/)

class Timer
{
public:
	Timer(const char* name) : name_(name), start(std::chrono::high_resolution_clock::now()) {}

	~Timer() {
		const auto diff {std::chrono::high_resolution_clock::now() - start};

		std::cout << name_ << " took " << std::chrono::duration<double, std::milli>(diff).count() << " ms\n";
	}

private:
	std::string name_;
	decltype(std::chrono::high_resolution_clock::now()) start {};
};

Then you can have:

{
    Timer t1 ("Selection Sort");
    selectionSort(array, array_size); 
}

and similar for each sort to time. Note that each type of sort is in it's own {} block.

[salem c]

You'll need arrays of thousands to millions to get the CPU to spend enough time for clock() to show any movement.

Don't go mad, because bubble sort will be monstrously slow compared to others, so you might need to stop testing with very large sizes for that.
Keep doubling the size until clock() starts noticing that some significant time is being spent.

[mbozzi]

Use a Timer class

Not that one, hopefully, because std::high_resolution_clock is a wall clock.

[JLBorges]

Also, std::chrono::high_resolution_clock may not be a monotonic (steady) clock.

Both processor time and real (wall clock) time are useful measures.
Boost Timer documentation:

For a production process, the wall clock time may be what is most important. To study the efficiency of code, total CPU time (user + system) is often a much better measure.

#include <iostream>
#include <chrono>
#include <type_traits>
#include <ctime>
#include <utility>
#include <iomanip>
#include <vector>
#include <numeric>
#include <algorithm>
#include <random>
#include <thread>

struct timer
{
    // we use the high resolution clock if it is monotonic, otherwise we use the steady clock
    using steady_wall_clock = std::conditional< std::chrono::high_resolution_clock::is_steady,
                                                std::chrono::high_resolution_clock,
                                                std::chrono::steady_clock >::type ;

    // return milliseconds elapsed: pair< processor_clock_millisecs, steady_wall_clock_millisecs >
    std::pair< long long, long long > elapsed()
    {
        const auto processor_clock_end = std::clock() ;
        const auto steady_wall_clock_end = steady_wall_clock::now() ;

        const long long processor_clock_millisecs = ( processor_clock_end - processor_clock_start ) * 1000.0 / CLOCKS_PER_SEC ;
        using namespace std::chrono ;
        const long long steady_wall_clock_millisecs = duration_cast<milliseconds>( steady_wall_clock_end - steady_wall_clock_start ).count() ;

        return { processor_clock_millisecs, steady_wall_clock_millisecs } ;
    }

    std::ostream& print_elapsed( std::ostream& stm = std::cout )
    {
        const auto [ processor_clock_millisecs, steady_wall_clock_millisecs ] = elapsed() ;
        return stm << "elapsed times in milliseconds:\n"
                   <<  "     processor: " << std::setw(12) << processor_clock_millisecs << '\n'
                   <<  "    wall clock: " << std::setw(12) << steady_wall_clock_millisecs << '\n' ;
    }

    void reset() { *this = {} ; }

    steady_wall_clock::time_point steady_wall_clock_start = steady_wall_clock::now() ;
    std::clock_t processor_clock_start = std::clock() ;
};

int main()
{
    // prepare some test data
    const std::size_t N = 1'000'000 ;
    std::vector<int> seq(N) ;
    std::iota( std::begin(seq), std::end(seq), 0 ) ;
    std::shuffle( std::begin(seq), std::end(seq), std::mt19937( std::random_device{}() ) ) ;

    // sort it and print out the elapsed times
    timer t ;
    std::sort( std::begin(seq), std::end(seq) ) ;

    // introduce some idle time to simulate processor time starvation
    using namespace std::literals ;
    std::this_thread::sleep_for( 100ms ) ;

    t.print_elapsed() ;
}

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