#include <iostream>
#include <array>
#include <ctime>
#include <cstdlib>
#include <vector>

using namespace std;




template <typename T>
int part(T & container,const int start,const int end)
{
    auto pivot = container[end];
    auto partitionIndex = start;

    for(int i = start; i < end; ++i)
    {
        if (container[i] <= pivot)
        {
            swap(container[i],container[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(container[partitionIndex],container[end]);

    return partitionIndex;
}

template <typename T>
void quickSort(T & container,const int start,const int end)
{
    if(start < end)
    {
        auto partitionIndex = part(container, start, end);
        quickSort(container,start,partitionIndex-1);
        quickSort(container,partitionIndex+1,end);

    }
}

template <typename T>
bool lessEqualSort(const T & container)
{
    for(int i = 0; i < container.size(); ++i)
    {
        for(int j = i; j <container.size(); ++j)
        {
            if (container[i] > container[j])
            {
                return false;
            }
        }
    }

    return true;
}

int main()
{
    const size_t SIZE{1000};

    array<int,SIZE>a{0};
    for(int i = 0; i <= SIZE; ++i)
    {
        a[i] = a[i-1] +1;
    }
    random_shuffle(&a[0] , &a[1000]);
    int start{0};
    int end{999};

//    vector<string>a{"Ryan","John","Daniel","Gavin","Frank","Danielle","Lucy","Sarah","Katie","Nicole"};
//    int start{0};
//    int end{9};

    for (const auto element : a)
    {
        cout << element << " ";
    }

    if(lessEqualSort(a)==true)
    {
        cout << endl;
        cout << "Sorted" << endl;
    }else
    {
        cout << endl;
        cout << "Unsorted" << endl;
    }


    quickSort(a, start, end);

    cout << endl;
    cout << "------------------------------------------------------" << endl;


    for (const auto element : a)
    {
        cout << element << " ";
    }

    if(lessEqualSort(a)==true)
    {
        cout << endl;
        cout << "Sorted" << endl;
    }else
    {
        cout << endl;
        cout << "Unsorted" << endl;
    }


    cout << endl;
    return 0;

}