Code

				
/*
Will Bergen
quick_sort.cpp
Implementation of Quick 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;


int qs_partition(vector<int> &input, int low, int high);
void qs(vector<int> &input, int low, int high);
void quick_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();
    quick_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);
}

int qs_partition(vector<int> &input, int low, int high) {
    int pivot = input[low];
    int i = low;
    for (int j = low + 1; j < high; j++) {
        if (input[j] <= pivot) {
            i++;
            swap(input[i], input[j]);
        }
    }
    swap(input[i], input[low]);
    return i;
}

void qs(vector<int> &input, int low, int high) {
    // int p;
    if (low < high) {
        int p = qs_partition(input, low, high);
        qs(input, low, p);
        qs(input, p+1, high);
    }
}

void quick_sort(){
    int num_swaps = 0;
    cout << "Running Quick Sort..." << endl;
    qs(a, 0, a.size());
}

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;
}