#include <iostream>
#include <string>
#include <vector>
#include <chrono>
#include <queue>
using namespace std;


//Let n be size of V, V.size()
//run time: O(n) (linear)
void printList(vector<double>& V) //run time: O(1)
{
    //run time of loop: #loops*costOfBody = n*O(1) = O(n)
    for (int i = 0; i < V.size(); i++) //#loops: n
        cout << V[i] << endl; //O(1)
}

//find and return the index of the smallest
//item within the given range.
//Let n be size of search range, n = end - start+1.
//run time: O(1)+O(1)+O(n)+O(1)= O(n) (linear)
int findSmallest(vector<double>& V, int start, int end) //O(1)
{
    int smallestSoFar = start; //O(1)

    //run time loop: n*O(1) = O(n)
    for (int i = start; i <= end; i++) //#loops: n
    {
        if (V[i] < V[smallestSoFar])  //O(1)
            smallestSoFar = i;
    }

    return smallestSoFar; //O(1)
}

//Let n = X.size()
//Run time: O(1)+O(n^2) = O(n^2)
void selectionSort(vector<double>& X) //O(1)
{
    //run time: n*(O(n)+O(1))= n*O(n)+n*O(1)=O(n^2)+O(n)= O(n^2)
    for (int i = 0; i < X.size(); i++) //#loops: n
    {
        int smallIndex = findSmallest(X, i, X.size() - 1); //O(n)
        swap(X[i], X[smallIndex]); //O(1)
    }
}

//Use a "heap" to sort a given
//vector of numbers.
//run time: O(n log n)
void heapSort(vector<double>& V) //O(1)
{
    priority_queue<double> H; //a heap

    //Step 1: put all the items into the heap
    //run time: n*O(log n) = O(n log n)
    for (int i = 0; i < V.size(); i++) //#loops: n
        H.push(V[i]);  //O(log n)

    //Step 2: extractMax from heap until empty
    //run time: n*(O(1)+O(log n) = O(n log n)
    for (int i = 0; i < V.size(); i++) //#loops n
    {
        V[i] = H.top(); //O(1)
        H.pop();  //O(log n)
    }

}


// In-place partition function using Lomuto partition scheme
// Run time: O(n), where n = high-low+1
template <typename T>
int partition(vector<T>& arr, int low, int high) {
    T pivot = arr[high]; // choose last element as pivot
    int i = low - 1;     // place for smaller elements

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // place pivot in correct position
    return i + 1; // return pivot index
}



//quicksort vector V from start to end
void quickSort(vector<double>& V, int start, int end)
{
    if (start >= end) //base case: list has 1 or fewer items)
    {
        //ha, don't do anything! easy!
    }
    else //list is bigger than 1
    {
        //pick a pivot and partition
        int p = partition(V, start, end);

        //quicksort left portion of list
        quickSort(V, start, p - 1);

        //quicksort right portion of list
        quickSort(V, p + 1, end);
    }
}


int main()
{

    //Sort test
    int huge = 1000000;
    vector<double> bigList;

    for (int i = 0; i < huge; i++)
    {
        //bigList.push_back(rand());
        bigList.push_back(rand());
    }

    auto start = chrono::high_resolution_clock::now();
    //selectionSort(bigList);
    //heapSort(bigList);
    quickSort(bigList,0, bigList.size()-1);
    auto finish = chrono::high_resolution_clock::now();

    //printList(bigList);

    chrono::duration<double> elapsed = finish - start;
    cout << "Algorithm took: " << elapsed.count() << endl;



	return 0;
}