serial_driver.cpp

/*
 * Created by William Wills on 3/29/23.
 *
 * This file contains the benchmark driver for our custom serial radix sort. The benchamark test cases were generated by
 * manually varying the MIN, MAX, and testSize variables.
 */

#include <iostream>
#include <random>

#include "SerialRadix.h"
#include "timer.c"

// Random class property of the UMBC CSEE department. buildRandomVector() function is my own code.
enum RANDOM {UNIFORM, NORMAL};
class Random {
public:
    Random(int min, int max, RANDOM type=UNIFORM) : m_min(min), m_max(max), m_type(type)
    {
        if (type == NORMAL){
            m_generator = std::mt19937(m_device());
            //the data set will have the mean of 50 and standard deviation of 20
            m_normdist = std::normal_distribution<>(50,20);
        }
        else{
            // Using a fixed seed value generates always the same sequence
            // of pseudorandom numbers, e.g. reproducing scientific experiments
            // here it helps us with testing since the same sequence repeats
            m_generator = std::mt19937(10);// 10 is the fixed seed value
            m_unidist = std::uniform_int_distribution<>(min,max);
        }
    }

    int getRandNum(){
        int result = 0;
        if(m_type == NORMAL){
            //returns a random number in a set with normal distribution
            //we limit random numbers by the min and max values
            result = m_min - 1;
            while(result < m_min || result > m_max)
                result = m_normdist(m_generator);
        }
        else{
            //this will generate a random number between min and max values
            result = m_unidist(m_generator);
        }
        return result;
    }

    void buildRandomVector(std::vector<int> &randomList){
        for (int & i : randomList){
            i = getRandNum();
        }
    }

private:
    int m_min;
    int m_max;
    RANDOM m_type;
    std::random_device m_device;
    std::mt19937 m_generator;
    std::normal_distribution<> m_normdist;//normal distribution
    std::uniform_int_distribution<> m_unidist;//uniform distribution

};


int main(){

    const int MIN = 10000;
    const int MAX = 99999;
    Random rand(MIN, MAX);


    std::cout << std::endl << "+++ small list smoke test +++" << std::endl;
    std::vector<int> smallTestNums = {123, 456, 789, 234, 567, 890};

    std::cout << std::endl << "list prior to sorting:" << std::endl;
    SerialRadix::printList(smallTestNums);

    SerialRadix::radixSort(smallTestNums);

    std::cout << std::endl << "sorted list:" << std::endl;
    SerialRadix::printList(smallTestNums);


    std::cout << std::endl << "+++ 50 size unit test +++" << std::endl;

    int testSize = 50;
    std::vector<int> list(testSize);
    rand.buildRandomVector(list);

    std::cout << std::endl << "list prior to sorting:" << std::endl;
    SerialRadix::printList(list);

    // sort the data
    SerialRadix::radixSort(list);

    std::cout << std::endl << "sorted list:" << std::endl;
    SerialRadix::printList(list);

    //validate sort
    int prevVal = 0;
    for (int i : list){
        if (i < prevVal){
            std::cerr << "out of order" << std::endl;
        }
        prevVal = i;
    }

    double start, stop, elapsed;
    testSize = 500000;

    std::cout << std::endl << "+++ " << testSize << " size unit test +++" << std::endl;

    std::cout << std::endl << "building random vector ->" << std::endl;
    list = std::vector<int>(testSize);
    rand.buildRandomVector(list);

    std::cout << "sorting list -> " << std::endl;

    GET_TIME(start)
    SerialRadix::radixSort(list);
    GET_TIME(stop)
    elapsed = stop - start;

    std::cout << "validating sort ->" << std::endl;

    //validate sort
    prevVal = 0;
    for (int i : list){
        if (i < prevVal){
            std::cerr << "out of order" << std::endl;
            return -1;
        }
        prevVal = i;
    }

    std::cout << "VALIDATED" << std::endl;
    std::cout << std::endl << "RUNTIME: " << elapsed << " seconds" << std::endl;
}