AP Statistics Project May 2023

data.csv

program.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>

#include "timer.hpp"

template<typename T>
void selection_sort(T* data, size_t n) {
    for(int i = 0; i < n; i++) {
        int idx = i;
        for(int j = i + 1; j < n; j++) {
            if(data[j] < data[idx]) {
                idx = j;
            }
        }

        std::swap(data[i], data[idx]);
    }
}

template<typename T> 
void insertion_sort(T* data, size_t n) {
    for(int i = 1; i < n; i++) {
        // insert this value
        for(int j = i; j >= 1; j--) {
            if(data[j - 1] > data[j]) {
                std::swap(data[j - 1], data[j]);
            } else {
                break;
            }
        }
    }
}

#define NUM_ARRS 1024
#define SAMP_SIZE 16
#define ARR_SIZE 128

void calc_stats(const std::vector<double> times, double& mean, double& stddev) {
    mean = 0.0;
    for(auto t : times) {
        mean += t;
    }
    mean /= NUM_ARRS;

    stddev = 0.0;
    for(auto t : times) {
        double dev = (t - mean);
        stddev += dev * dev;
    }
    stddev /= (NUM_ARRS - 1);
    stddev = sqrt(stddev);
}

int main() {
    srand(0);

    std::ofstream csv("data.csv");
    csv << "selection_sort_time,insertion_sort_time\n";

    std::vector<double> sv, iv;

    for(int i = 0; i < NUM_ARRS; i++) {
        // gen random array
        int src[ARR_SIZE], test[ARR_SIZE];
        for(int j = 0; j < ARR_SIZE; j++) {
            src[j] = rand();
        }

        double sdur = 0.0, idur = 0.0;
        Timer stopwatch;

        for(int j = 0; j < SAMP_SIZE; j++) {
            std::copy_n(src, ARR_SIZE, test);

            stopwatch.start();
            selection_sort(test, ARR_SIZE);
            stopwatch.stop();
            sdur += stopwatch.duration();
        }
        sdur /= SAMP_SIZE;

        for(int j = 0; j < SAMP_SIZE; j++) {
            std::copy_n(src, ARR_SIZE, test);

            stopwatch.start();
            insertion_sort(test, ARR_SIZE);
            stopwatch.stop();
            idur += stopwatch.duration();
        }
        idur /= SAMP_SIZE;
        
        //std::cout << sdur << '\t' << idur << '\t' << sdur - idur << '\n';
        csv << sdur << ',' << idur << '\n';
        sv.push_back(sdur);
        iv.push_back(idur);
    }

    csv.close();

    // paired t-test
    double smean, sstddev;
    double imean, istddev;

    calc_stats(sv, smean, sstddev);
    calc_stats(iv, imean, istddev);

    std::vector<double> diff(NUM_ARRS);
    for(int i = 0; i < NUM_ARRS; i++) {
        diff[i] = sv[i] - iv[i]; // s - i
    }

    double dmean, dstddev;
    calc_stats(diff, dmean, dstddev);

    double t = dmean / (dstddev / sqrt(NUM_ARRS));
    
    std::cout << "smean:\t" << smean << '\n';
    std::cout << "sstddev:\t" << sstddev << '\n';
    std::cout << "imean:\t" << imean << '\n';
    std::cout << "istddev:\t" << istddev << '\n';
    std::cout << "dmean:\t" << dmean << '\n';
    std::cout << "dstddev:\t" << dstddev << '\n';
    std::cout << "t:\t" << t << '\n';
    std::cout << "df:\t" << NUM_ARRS - 1 << '\n';

    return 0;
}

timer.hpp

#pragma once

#include <chrono>

// basically a stopwatch in C++
// returns a double time in seconds
class Timer {
public:
    using clock = std::chrono::system_clock;
    using time_point = std::chrono::time_point<clock>;

    Timer() {}

    void start() {
        tstart = now();
    }

    double lapse() {
        return calc_duration(tstart, now());
    }

    double stop() {
        tend = now();
        return duration();
    }

    double duration() {
        return calc_duration(tstart, tend);
    }

    double restart() {
        double time = stop();
        start();
        return time;
    }
private:
    double calc_duration(time_point t1, time_point t2) {
        std::chrono::duration<double> dt = t2 - t1;
        return dt.count();
    }

    time_point now() {
        return clock::now();
    }

    time_point tstart;
    time_point tend;
};