Timing std::sort - live coding in class 2024.1.10

main.cpp

// Written by Mason during class on 2024.10.1

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <iostream>

using namespace std;

void randomizeVector(vector<int> &v) {
    size_t vsize = v.size();
    for (size_t i = 0; i < vsize; i++) {
        v[i] = rand();
    }
}

clock_t timeSort(int numRuns, int vecSize) {
    vector<int> v;
    v.resize(vecSize);
    
    clock_t timeTotal = 0;
    
    int currentRuns = 0;
    
    while (currentRuns < numRuns) {
        randomizeVector(v);
        
        clock_t t1 = clock();
        sort(v.begin(), v.end());
        clock_t t2 = clock();
        
        timeTotal += t2 - t1; // delta time
        
        currentRuns++;
    }
    
    return timeTotal / numRuns;
}

int main()
{
    int vecSize = 100000;
    int times = 25; // so we go until 10^(times-1)
    
    for (int i = 0; i < times; i++) {
        cout << vecSize << "," << timeSort(10, vecSize) << "\n";
        vecSize += 1000000 / times;
    }
    

    return 0;
}

pseudocode.txt

I wrote this before starting the c++ implementation.

includes: ctime (clock), algorithm (sort), vector, cstdlib (rand)

function: randomizeVector
- takes in a vector reference/pointer
- replaces each element with a new rand() value

function: timeSort
- take in the number of times to run
- takes in a vector size and makes a vector of that size
- calls randomizeVector
- store time1
- call library sort
- store time2
- calculate delta time and add it to a running total
- optional: verify that sorting was correct - adds O(n) time but that should be relatively insignificant
- repeat until we've run enough times
- return running total divided by number of times run

function: main
- go from 100 to 1_000_000, multiplying the vector size by 10 each time
- call timeSort for each with 100 trials
- log the vector size and the time taken on average