#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

const int n = 25000;
vector<string> selectionSorted(int n, vector<string>);
vector<string> mergeSort(vector<string> &L, int a, int b);
vector<string> merge(const vector<string> &left, const vector<string> &right);
void quickSort(std::vector<string> &L, int a, int b);


int main() {
    ifstream inFile;

    inFile.open("shuffled.txt");

    vector<string> words;
    string line;


    while (inFile >> line)
    {
        words.push_back(line);
    }
    inFile.close();



    cout << "Original List: ";
    for(int i = 0; i < words.size(); i++)
    {
        cout << words[i] << " ";
    }
    cout << endl;

    //selection sort
    selectionSorted(n,words);


    words.clear();



    inFile.open("shuffled.txt");
    while (inFile >> line) {
        words.push_back(line);
    }
    cout << words.size() << endl;
    inFile.close();


    //merge sort
    //mergeSort(words);
    //auto sorted = mergeSort(words,0,0);
    mergeSort(words,0,-1);

    vector<string> &sorted1 = words;

    cout << "Merge Sort Sorted: ";
    for(int i = 0; i < words.size(); i++)
    {
        cout << words[i] << " ";
    }
    cout << endl;


    //quick sort
    int l,r,i,n;
    quickSort(words,0,n - 1);
    cout << "Quick Sort Sorted: ";
    for(i = 0; i < words.size(); i++)
    {
        cout << words[i] << " ";
    }
    cout << endl;
    //getch();


    return 0;
}

vector<string> selectionSorted(int n, vector<string> words)
{
    for (int pass = 0; pass <= n - 2; ++pass)
    {

        int minIndex = pass;
        for (int i = minIndex + 1; i < n; i++)
        {
            if (words[i] < words[minIndex])
            {
                minIndex = i;

            }
        }
        swap(words[pass], words[minIndex]);
    }
    cout << "Selection sort sorted: ";
    for (auto x : words)
        cout << x << " ";
    cout << "\n";

    return words;
}

vector<string> mergeSort(vector<string> &L, int a, int b)
{
    if (b == -1)
        b = L.size();

    const int k = b - a;


    if (k == 1)
        return { L[a] };
    else if (k == 0)
        return { };

    int m = (a + b) / 2;
    vector<string> left  = mergeSort(L, a, m), right = mergeSort(L, m, b);

    return merge(left, right);
}

vector<string> merge(const vector<string> &left, const vector<string> &right) {
    int l = 0, r = 0;

    vector<string> v;
    v.reserve(left.size() + right.size());
    while (l < left.size() || r < right.size())
    {
        if (r >= right.size() || (l < left.size() && left[l] <= right[r]))
        {
            v.push_back(left[l]);
            ++l;
        }
        else
        {
            v.push_back(right[r]);
            ++r;
        }
    }

    return v;
}

void quickSort(std::vector<string> &L, int a, int b)
{
    if (b == -1)
        b = L.size();

    const int k = b - a;

    // If the list is empty or has just one element, it's already sorted
    if (k <= 1)
        return;

    // Now, the actual quick sort —

    // Select a pivot
    // For now, use the first element as the pivot

    // piv: index of the pivot element
    int piv = a;

    // Pivot the list (move elements less than the pivot to before it, and ones
    // greater than the pivot after it)
    swap(L[piv], L[a]); // move pivot to first element
    piv = a; // since I moved the pivot, update piv

    for (int i = piv + 1; i < b; ++i)
    {


        // If it's ≥, we don't need to do anything because it's already on the
        // right side of the pivot
        if (L[i] < L[piv])
        {
            // Swap with element to the right of the pivot
            swap(L[i], L[piv + 1]);
            // Swap it with the pivot
            swap(L[piv], L[piv + 1]);
            ++piv; // moved the pivot one to the right
        }
    }

    // done pivoting — next step is to sort each half
    quickSort(L, a, piv);
    quickSort(L, piv + 1, b);


}