// Quicksort - see makefile for compiling options with G++.
// Will not compile in VS2012 due to initialiser syntax in main() for std::vector
#include <iostream>
#include <vector>
#include <algorithm>    // Required
#include <iterator> //Required
#include <stdlib.h> // Required
#include <time.h>   // Required

// Function Prototypes
int randomNumber(int start, int end);   // Generate a number between start and end

// Perform QuickSort
// Data provided will be modified
template <typename Iterator> void quickSort(Iterator start, Iterator end){
    int size = (end - start);
    if ( size <= 0 )
        return;     // Base case

    // Partition - in place partitioning that involves only swapping
    // https://class.coursera.org/algo/lecture/preview/22 - O(n) time with no extra memory++
    /*
        Assume pivot is first element of array
        Otherwise swap pivot with first element

        Idea: Array A is in this form
            pivot | < p | > p | unpartitioned/unseen

        Let i = index of the first item > p
        Let j = index of the first item unpartitioned

        Let i = 1
        Let j = 1
        Let p = pivot value

        for j < size
            if A[i] < p
                swap A[j] with A[i]
                i++
        swap A[0] with A[i-1]
    */
    // Get pivot element
    int pivotIndex = randomNumber(0, size);
    typename std::iterator_traits<Iterator>::value_type pivot = *(start + pivotIndex);

    if (pivotIndex != 0)
        std::swap(*(start + pivotIndex), *start);

    int i = 1;
    for (int j = 1; j < size; j++){
        if ( *(start + j) < pivot ){
            std::swap( *(start+j), *(start+i));
            i++;
        }
    }

    std::swap(*start, *(start + i - 1));

    quickSort(start, start+i-1);
    quickSort(start+i, end);
}

int main(){
    // This is C++11 syntax
    // Input must be unsigned
    std::vector<unsigned> input = {5,10,15,20,25,50,40,30,20,10,9524,878,17,1,99,18785,3649,164,94,
        123,432,654,3123,654,2123,543,131,653,123,533,1141,532,213,2241,824,1124,42,134,411,
        491,341,1234,527,388,245,1992,654,243,987};

    quickSort(input.begin(), input.end());

    // C++11 ranged based for loops
    // http://www.cprogramming.com/c++11/c++11-ranged-for-loop.html
    for (unsigned it : input){
        std::cout << it << std::endl;
    }

    return 0;
}

// Generate a number between start and end
int randomNumber(int start, int end){
    // Seed the randomiser
    srand( time(NULL) );

    return rand() % end + start;
}