Code

				
/*
Will Bergen
insertion_sort.cpp
Implementation of Insertion sort on a randomly filled vector, timed with high res clock
chrono is from C++11, so compile with -std=gnu++11
*/

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

void insertion_sort();
void pretty_print(vector<int> array);
void swap(int &in1, int &in2);
void rand_fill();

int aSize = 500; // Size of array to sort
vector<int> a; // Array to sort

int main() {
    // Randomly Fill Array:
    rand_fill();

    // Print Array before sorting:
    // pretty_print(a);

    // Time and Execute Sort:
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    insertion_sort();
    high_resolution_clock::time_point t2 = high_resolution_clock::now();

    // Print Time:
    cout << "Operation Finished in " << duration_cast<microseconds>(t2-t1).count()*.000001 << " Seconds." << endl;

    // Print Array after sorting:
    // pretty_print(a);
}

void insertion_sort() {
    cout << "Running Insertion Sort..." << endl;

    // cout << a.size() << endl;
    for (int i = 0; i < a.size(); ++i)
    {
        int j = i;
        while (j > 0 && a[j-1] > a[j]) {
            swap(a[j], a[j-1]);
            j = j -1;
        }
        // pretty_print(a);
    }
}

void swap(int &in1, int &in2) {
    int temp = in1;
    in1 = in2;
    in2 = temp;
}

void rand_fill() {
    srand(time(NULL)); // Seed once
    for (int i = 0; i<aSize; i++){
        a.push_back((rand() % 100)+1); // nums 1-100
    }
}


void pretty_print(vector<int> array) {
    for (int i = 0; i < array.size()-1; ++i)
    {
        cout << array[i] << ",";
    }
    cout << array[array.size()-1] << endl;
}