#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cmath>
#include <algorithm>

using namespace std;


static void RandomArray(int *A, int n) { //случайный массив
    for (int i = 0; i < n; i++)
        A[i] = rand() % 50 + 1;
}

static void AscendingArray(int *A, int n) { //возрастающий упорядоченный массив
    for (int i = 0; i < n; i++)
        A[i] = i;
}

static void DescendingArray(int *A, int n) { //убывающий упорядоченный массив
    for (int i = n - 1; i >= 0; i--)
        A[i] = i;
}


static void IndArray(int *Ind, int n) { //заполнение массива индексов
    for (int i = 0; i < n; i++)
        Ind[i] = i;
}


class Sort {

private:

    static bool SortCheck(int *A, int n) { //проверка массива на сортировку
        for (int i = 0; i < n-1; i++) {
            if (A[i] > A[i + 1])
                return false;
        }
        return true;
    }

    static bool SortCheckIndex(int *A, int *Ind, int n) { //проверка косвенного массива на сортировку
        for (int i = 0; i < n - 1; i++) {
            if (A[Ind[i]] > A[Ind[i + 1]])
                return false;
        }
        return true;
    }


    static void MergeSeries(int *A, int b, int c, int e, int *D) { //слияние серий A[b..c] и A[c+1..e] в массив D[b..e]
        int i = b, j = c + 1, k; //i, j, k хранят номера текущих элементов в двух сериях и массиве D

        for (k = b; k <= e; k++)
            if (j > e)
                D[k] = A[i++];
            else if (i > c)
                D[k] = A[j++];
            else if (A[i] <= A[j])
                D[k] = A[i++];
            else D[k] = A[j++];
    }


    static void SiftHeap(int *A, int i, int m) { //функция проссеивания в пирамиде
        int j = i, k = i * 2 + 1; // k - номер левого сына
        while (k <= m) {
            if (k < m && A[k] < A[k + 1])
                k++; //больший сын
            if (A[j] < A[k]) {
                int tmp = A[j];
                A[j] = A[k];
                A[k] = tmp;
                j = k;
                k = k * 2 + 1;
            }
            else
                break;
        }
    }


    static void QuickSortRec(int *A, int *Ind, int b, int e) { //рекурсивный вызов косвенной быстрой сортировки
        int x; //опорный элемент
        int i, j, c = b, d = e;

        while (c < d) {
            x = A[Ind[(c + d) / 2]]; i = c; j = d;
            while (i < j) {
                while (A[Ind[i]] < x) i++;
                while (A[Ind[j]] > x) j--;
                if (i <= j) {
                    int tmp = Ind[i];
                    Ind[i] = Ind[j];
                    Ind[j] = tmp;
                    i++;
                    j--;
                }
            }

            if (j - c < d - i) {
                if (c < j)
                    QuickSortRec(A, Ind, c, j);
                c = i;
                }
            else {
                if (i < d)
                    QuickSortRec(A, Ind, i, d);
                d = j;
            }
        }
    }


public:

    static void MergeSort(int *A, int n) { //рекуррентное слияние
        unsigned int start_time = clock(); // начальное время

        int s, b, c, e; //s - текущая длина серий в массиве, b, c, e - задают границы сливаемых серий
        int *D = new int[n];

        for (s = 1; s < n; s *= 2) {
            for (b = 0; b < n; b += s * 2) {
                c = min(b + s - 1, n - 1);
                e = min(c + s, n - 1);
                MergeSeries(A, b, c, e, D);
            }
            for (b = 0; b < n; b++) //копирование отсортированного массива
                A[b] = D[b];
        }

        unsigned int end_time = clock(); // конечное время
        unsigned int search_time = end_time - start_time; // искомое время
        cout << "Performance of the MergeSort is: " << search_time << "ms" << endl;

        if (SortCheck(A, n)) //Проверка сортировки
            cout << "Array is sorted" << endl << endl;
        else
            cout << "Array isn't sorted" << endl << endl;
        delete[] D;
    }


    static void ShellSort(int *A, int *Ind, int n) { //косвенная сортировка Шелла
        unsigned int start_time = clock();

        int i, j, h;
        for (h = 1; h <= n / 9; h = h * 3 + 1); //вычисляем начальное значение h (h-цепочки – последовательности элементов с индексами)
        while (h >= 1) {
            for (i = h; i < n; i++)
                for (j = i - h; j >= 0 && A[Ind[j]] > A[Ind[j + h]]; j -= h) {
                    int tmp = Ind[j];
                    Ind[j] = Ind[j + h];
                    Ind[j + h] = tmp;
                }
            h = (h - 1) / 3;
        }

        unsigned int end_time = clock(); // конечное время
        unsigned int search_time = end_time - start_time; // искомое время
        cout << "Performance of the ShellSort is: " << search_time << "ms" << endl;

        for (int i = 0; i < n; i++) {
            cout << A[i] << " " << Ind[i] << endl;

        }

        if (SortCheckIndex(A, Ind, n)) //Проверка сортировки
            cout << "Array is sorted" << endl << endl;
        else
            cout << "Array isn't sorted" << endl << endl;
    }


    static void HeapSort(int *A, int n) { //пирамидальная сортировка
        unsigned int start_time = clock(); // начальное время
        int i, m;

        for (i = n / 2; i >= 0; i--) //построение пирамиды
            SiftHeap(A, i, n - 1);

        for (m = n - 1; m >= 1; m--) { //сортировка массива
            int tmp = A[0];
            A[0] = A[m];
            A[m] = tmp;
            SiftHeap(A, 0, m-1);
        }

        unsigned int end_time = clock(); // конечное время
        unsigned int search_time = end_time - start_time; // искомое время
        cout << "Performance of the HeapSort is: " << search_time << "ms" << endl;

        if (SortCheck(A, n))
            cout << "Array is sorted" << endl << endl;
        else
            cout << "Array isn't sorted" << endl << endl;
    }


    static void QuickSort(int *A, int *Ind, int n) { //косвенная быстрая сортировка
        unsigned int start_time = clock(); // начальное время

        QuickSortRec(A, Ind, 0, n - 1);

        unsigned int end_time = clock(); // конечное время
        unsigned int search_time = end_time - start_time; // искомое время
        cout << "Performance of the QuickSort is: " << search_time << "ms" << endl;

        if (SortCheckIndex(A, Ind, n)) //Проверка сортировки
            cout << "Array is sorted" << endl << endl;
        else
            cout << "Array isn't sorted" << endl << endl;
    }
};


int main()  {
    srand(time(0));

    int n;
    cout << "Enter the size of array" << endl;
    cin >> n;
    int *A = new int[n];
    int *Ind = new int[n];

    cout << "Merge Sorting Random Array " << endl;
    RandomArray(A, n);
    Sort::MergeSort(A, n);
    cout << "Merge Sorting Ascending Array " << endl;
    AscendingArray(A, n);
    Sort::MergeSort(A, n);
    cout << "Merge Sorting Descending Array " << endl;
    DescendingArray(A, n);
    Sort::MergeSort(A, n);

    cout << "Shell Sorting Random Array " << endl;
    RandomArray(A, n);
    IndArray(Ind, n);
    Sort::ShellSort(A, Ind, n);
    cout << "Shell Sorting Ascending Array " << endl;
    AscendingArray(A, n);
    IndArray(Ind, n);
    Sort::ShellSort(A, Ind, n);
    cout << "Shell Sorting Descending Array " << endl;
    DescendingArray(A, n);
    IndArray(Ind, n);
    Sort::ShellSort(A, Ind, n);

    cout << "Heap Sorting Random Array " << endl;
    RandomArray(A, n);
    Sort::HeapSort(A, n);
    cout << "Heap Sorting Ascending Array " << endl;
    AscendingArray(A, n);
    Sort::HeapSort(A, n);
    cout << "Heap Sorting Descending Array " << endl;
    DescendingArray(A, n);
    Sort::HeapSort(A, n);

    cout << "Quick Sorting Random Array " << endl;
    RandomArray(A, n);
    IndArray(Ind, n);
    Sort::QuickSort(A, Ind, n);
    cout << "Quick Sorting Ascending Array " << endl;
    AscendingArray(A, n);
    IndArray(Ind, n);
    Sort::QuickSort(A, Ind, n);
    cout << "Quick Sorting Descending Array " << endl;
    DescendingArray(A, n);
    IndArray(Ind, n);
    Sort::QuickSort(A, Ind, n);

    return 0;
}