#include <iostream>
#include <algorithm>
#include <ctime>
#include <random>
#include <vector>
#include <chrono>

void bubbleSort(std::vector<int> &);

void insertionSort1(std::vector<int> &);

void insertionSort2(std::vector<int> &);

void selectionSort(std::vector<int> &);

bool checkIfSorted(std::vector<int> &);

void bubbleSort2(std::vector<int> &);

void bubbleSort3(std::vector<int> &);

void shellSort1(std::vector<int> &);

void shellSort2(std::vector<int> &);

void quickSort1(std::vector<int> &tab, int l, int r);

void quickSortRandom(std::vector<int> &, int, int);

void quickSortMedian(std::vector<int> &, int, int);

void quickSortAndInsertion(std::vector<int> &, int, int);

static std::random_device randomDevice;
static std::mt19937 generator(randomDevice());


int main() {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 1000000);
    const int tabSize = 128000;
    std::vector<int> tab;
    for (int i = 0; i < tabSize; ++i) {
        tab.push_back(dis(gen));
    }
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
//    bubbleSort(tab);
//    selectionSort(tab);
//    insertionSort1(tab);
//    insertionSort2(tab);
//    bubbleSort2(tab);
//    bubbleSort3(tab);
//    quickSort1(tab, 0, (int) tab.size());
//    quickSortRandom(tab, 0, (int) tab.size());
//    quickSortMedian(tab, 0, (int) tab.size());
    quickSortAndInsertion(tab, 0, (int)tab.size());
//    shellSort1(tab);
//    shellSort2(tab);

    std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    std::cout << std::endl
              << "Duration of the sorting algorithm: "
              << duration << std::endl;

    if (checkIfSorted(tab)) printf("Array is sorted correctly.");
    return 0;
}


void shellSort1(std::vector<int> &tab) {
    int h = 1;
    while (h < tab.size() / 9) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (int i = h; i < tab.size(); i++) {
            int x = tab[i];
            int j = i;
            while (j >= h && x < tab[j - h]) {
                tab[j] = tab[j - h];
                j = j - h;
            }
            tab[j] = x;
        }
        h = h / 3;
    }
}

void shellSort2(std::vector<int> &tab) {
    int h = static_cast<int>(tab.size() / 2);
    while (h > 0) {
        for (int i = h; i < tab.size(); i++) {
            int x = tab[i];
            int j = i;
            while (j >= h && x < tab[j - h]) {
                tab[j] = tab[j - h];
                j = j - h;
            }
            tab[j] = x;
        }
        h = h / 2;
    }
}

void quickSort1(std::vector<int> &tab, int l, int r) {
    if (l < r) {
        int pivot = tab[l];
        int s = l;
        for (int i = l; i <= r; i++) {
            if (tab[i] < pivot) {
                s++;
                std::swap(tab[s], tab[i]);
            }
        }
        std::swap(tab[l], tab[s]);
        quickSort1(tab, l, s - 1);
        quickSort1(tab, s + 1, r);
    }
}

void quickSortRandom(std::vector<int> &tab, int l, int r) {
    if (l < r) {
        std::uniform_int_distribution<> dis(l, r);
        int pivot_elem = dis(generator);
        // Set pivot to first element:
        std::swap(tab[l], tab[pivot_elem]);


        int pivot = tab[l];
        int s = l;
        for (int i = l; i <= r; i++) {
            if (tab[i] < pivot) {
                s++;
                std::swap(tab[s], tab[i]);
            }
        }
        std::swap(tab[l], tab[s]);
        quickSortRandom(tab, l, s - 1);
        quickSortRandom(tab, s + 1, r);
    }
}

void quickSortMedian(std::vector<int> &tab, int l, int r) {
    if (l < r) {
        int j = r - 1;
        int k = j / 2;
        if (tab[j] < tab[k]) std::swap(tab[j], tab[k]);

        if (tab[j] < tab[l]) std::swap(tab[j], tab[l]);

        if (tab[k] < tab[l]) std::swap(tab[k], tab[l]);

        // Set pivot to the first element:
        std::swap(tab[l], tab[k]);


        int pivot = tab[l];
        int s = l;
        for (int i = l; i <= r; i++) {
            if (tab[i] < pivot) {
                s++;
                std::swap(tab[s], tab[i]);
            }
        }
        std::swap(tab[l], tab[s]);
        quickSortMedian(tab, l, s - 1);
        quickSortMedian(tab, s + 1, r);
    }
}

void quickSortInsert(std::vector<int> &arr, int l, int r) {
    int temp, j;
    for (int i = l; i < r; i++) {
        temp = arr[i];
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > temp)
                arr[j + 1] = arr[j];
            else
                break;
        }
        arr[j + 1] = temp;
    }
}

void quickSortAndInsertion(std::vector<int> &tab, int l, int r) {
    if (l < r) {
        if ((r - l) < 10) {
            quickSortInsert(tab, l, r + 1);
        } else {
            int t = tab[l];
            int s = l;
            for (int i = l; i <= r; i++) {
                if (tab[i] < t) {
                    s++;
                    std::swap(tab[s], tab[i]);
                }
            }
            std::swap(tab[l], tab[s]);
            quickSortAndInsertion(tab, l, s - 1);
            quickSortAndInsertion(tab, s + 1, r);
        }
    }
}


void bubbleSort3(std::vector<int> &table) {
    bool change = false;
    int lastChangedPosition = 0;
    do {
        for (int i = lastChangedPosition; i < table.size() - 1; i++) {
            if (table[i] > table[i + 1]) {
                std::swap(table[i], table[i + 1]);
                change = true;
                lastChangedPosition = i;
            }
        }
        if (!change)
            break;
        change = false;
        for (int i = lastChangedPosition - 1; i >= 0; i--) {
            if (table[i] > table[i + 1]) {
                std::swap(table[i], table[i + 1]);
                change = true;
                lastChangedPosition = i;
            }
        }
    } while (change);
}

void bubbleSort2(std::vector<int> &table) {
    bool change;
    for (int i = 0; i < table.size(); ++i) {
        change = false;
        for (int j = 1; j < table.size(); ++j) {
            if (table[j - 1] > table[j]) {
                std::swap(table[j - 1], table[j]);
                change = true;
            }
        }
        if (!change)
            break;
    }
}


void insertionSort2(std::vector<int> &table) {
    int valueMin = table[0];
    int minIdx = 0;
    int j;
    for (int i = 1; i < table.size(); ++i) {
        if (valueMin > table[i]) {
            minIdx = i;
            valueMin = table[i];
        }
    }
    std::swap(table[0], table[minIdx]);
    for (int i = 1; i < table.size(); ++i) {
        valueMin = table[i];
        j = i - 1;
        while (valueMin < table[j]) {
            table[j + 1] = table[j];
            j = j - 1;
        }
        table[j + 1] = valueMin;
    }
}

void insertionSort1(std::vector<int> &table) {
    int valueMin;
    int j;
    for (int i = 1; i < table.size(); ++i) {
        valueMin = table[i];
        j = i - 1;
        while ((j >= 0) && (valueMin < table[j])) {
            table[j + 1] = table[j];
            j = j - 1;
        }
        table[j + 1] = valueMin;
    }
}


void selectionSort(std::vector<int> &table) {
    int indexMin, value_min;
    for (int i = 0; i < (table.size() - 1); ++i) {
        indexMin = i;
        value_min = table[i];
        for (int j = (i + 1); j < table.size(); ++j) {
            if (table[j] < value_min) {
                indexMin = j;
                value_min = table[j];
            }
        }
        std::swap(table[i], table[indexMin]);
    }
}


void bubbleSort(std::vector<int> &table) {
    for (int i = 0; i < table.size(); ++i) {
        for (int j = 1; j < table.size(); ++j) {
            if (table[j - 1] > table[j]) {
                std::swap(table[j - 1], table[j]);
            }
        }
    }
}

bool checkIfSorted(std::vector<int> &arr) {
    int i = 1;
    int is_sorted = 1;
    while ((i < arr.size()) && is_sorted) {
        if (arr[i - 1] > arr[i])
            is_sorted = 0;
        i++;
    }
    return static_cast<bool>(is_sorted);
}