#include "Insert.h";
#include "QuickSort.h";
#include "QuickSortLeft.h";
#include "QuickSort3.h";
#include "QuickSort4.h";
 
#include "Timer.h";
#include "RandomGenerator.h";
 
int main()
{
    srand( (unsigned)time(NULL));
 
    // Начальный массив, нужен лишь для инициализации
    int* _x;
 
    // Количество размерностей массивов
    const int sizeNum   = 5;
    int sizes[sizeNum] = {4000, 8000, 10000, 15000, 20000};
 
    // Количество видов сортировок
    const int sortTypeNum = 4;
 
    // Инициируем различные виды быстрой сортировки 
    QuickSort      QSortCenterObj(0, _x);
    QuickSortLeft  QSortLeftObj(0, _x);
    QuickSort3     QSort3Obj(0, _x);
    QuickSort4     QSort4Obj(0, _x, 10);
 
 
    // Им будем подсчитывать время
    Timer timerObj(sortTypeNum);
 
    Sort* sorts[sortTypeNum];
    sorts[0] =& QSortCenterObj;
    sorts[1] =& QSortLeftObj;
    sorts[2] =& QSort3Obj;
    sorts[3] =& QSort4Obj;
 
    // Цикл по 2 режимам состава массивов:
    // случайные / частично-отсортированные числа
    for (int k = 0; k < 2; k++) {
        if (0 == k) cout << "I. Random Numbers";
        else cout << "II. PARTLY Random Numbers";
        cout << endl;
 
        // Цикл по размерам массива
        for (int i = 0; i < sizeNum; i++) {
            cout << "  " << i + 1 << ") Array Size(N): " << sizes[i] << "\n";
 
            // ... по видам сортировок
            for (int j = 0; j < sortTypeNum; j++) {
                int N  = sizes[i];
                int* x = new int[N];
                RandomGenerator genObj(N);
 
                // В зависимости от режима - заполняем исходный массив
                if (0 == k) x = genObj.GetRandom(0, 100);
                else        x = genObj.GetPartSorted(N/10, N/5);
 
                // Уточняем размер и передаем исходный сформированный массив
                sorts[j]->setSize(N);
                sorts[j]->setArr(x);
 
                // Засекаем время
                timerObj.Start(0);
                sorts[j]->Run();    // Прогоняем сортировку текущего вида
                float exTime = timerObj.Get(0, 1); // Фиксируем время
 
                // Выводим время выполнения и количество перестановок
                cout.setf(ios::fixed | ios::showpoint);
                cout << "     " << exTime << " sec.:: ";
                cout.width(8);
                cout << sorts[j]->getSwapNum() << " swaps :: " << sorts[j]->getName() << "\n";
 
                delete [] x;
            }
            cout << "\n";
        }
        cout << "\n\n";
    }
 
    return 0;
}

#pragma once
#include "quicksort.h"
 
class QuickSortLeft :
    public QuickSort
{
public:
    QuickSortLeft(int, int*);
    void Run(void);
    void Launch(int*, int, int);
public:
    ~QuickSortLeft(void);
};
 

#include "QuickSortLeft.h"
 
QuickSortLeft::QuickSortLeft(int n, int* x) : QuickSort(n, x) {
    this->algName = "Quick Sort [Left]";
}
 
void QuickSortLeft::Run(void)
{
    return this->Launch(this->x, 0, (this->n - 1));
}
 
void QuickSortLeft::Launch(int* x, int l, int u) {
    // Отбрасываем пустые и 
    // одноэлементные массивы
    if (l >= u) {
        return;
    }
 
    int tmp;
    int m = l;
    for (int i = l+1; i <= u; i++) {
 
        if (x[i] < x[l]) {
            // делаем swap(++m, i)
            tmp = x[++m]; x[m] = x[i]; x[i] = tmp;
            this->CountSwap();
        }
    }
 
    // Делаем swap(l, m):
    // Без этого - алгоритм может войти
    // в бесконечную рекурсию
    tmp = x[l]; x[l] = x[m]; x[m] = tmp;
    this->CountSwap();
 
    // вызываем реккурсивно 
    // для 2-х полученных областей
    this->Launch(x, l, m-1);
    this->Launch(x, m+1, u);
}
 
QuickSortLeft::~QuickSortLeft(void)
{
}
 

#pragma once
#include "quicksort.h"
 
class QuickSort3 :
    public QuickSort
{
public:
    QuickSort3(int, int*);
    void Run(void);
    void Launch(int, int);
public:
    ~QuickSort3(void);
};
 

#include "QuickSort3.h"
 
QuickSort3::QuickSort3(int n, int* x) : QuickSort(n, x) {
    this->algName = "Quick Sort [Left] optimized";
}
 
void QuickSort3::Run(void)
{
    this->Launch(0, (this->n - 1));
}
 
void QuickSort3::Launch(int l, int u) {
    if (l >= u)
        return;
 
    int t, tmp;
    int i,j;
    t = this->x[l]; i = l; j = u+1;
 
    while (1) {
        /* пропуск элементов справа и слева,
           чтобы не делать лишней работы */
        do i++; while (i <= u && this->x[i] < t);
        do j--; while (this->x[j] > t);
 
        if (i > j)
            break;
        // Делаем swap(i, j):
        tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
        this->CountSwap();
    }
 
    // swap(l, j)
    tmp = this->x[l]; this->x[l] = this->x[j]; this->x[j] = tmp;
    this->CountSwap();
 
    this->Launch(l, j-1);
    this->Launch(j+1, u);
}
 
QuickSort3::~QuickSort3(void)
{
}
 

#pragma once
#include "quicksort.h"
 
class QuickSort4 :
    public QuickSort
{
private:
    int cutoff;
public:
    QuickSort4(int, int*, int);
    void Run(void);
    void Launch(int, int);
    int GetRand(int, int);
    unsigned int getCutoff(void);
    void setCutoff(unsigned int);
public:
    ~QuickSort4(void);
};
 

#include "QuickSort4.h"
#include "time.h";
 
QuickSort4::QuickSort4(int n, int* x, int cutoff) : QuickSort(n, x) {
    this->algName = "Quick Sort [Rand Choice] Optimized";
    this->cutoff = cutoff;
}
 
void QuickSort4::Run(void)
{
    this->Launch(0, (this->n - 1));
 
    // Заключительная сортировка вставкой
    this->simpleSortObj.setArr(this->x);
    this->simpleSortObj.setSize(this->n);
    this->simpleSortObj.Run();
 
    // Не забываем посчитать swap-ы сделанные им
    this->swapNum += this->simpleSortObj.getSwapNum();
}
 
void QuickSort4::Launch(int l, int u) {
    if (u - l < this->cutoff)
        return;
 
    this->Swap(l, this->GetRand(l, u));
    int t;
    int i,j;
    t = this->x[l]; i = l; j = u+1;
 
    while (1) {
        /* пропуск элементов справа и слева,
           чтобы не делать лишней работы */
        do i++; while (i <= u && this->x[i] < t);
        do j--; while (this->x[j] > t);
 
        if (i > j)
            break;
        // Делаем swap(i, j):
        int tmp;
        tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
        this->CountSwap();
    }
 
    this->Swap(l, j);
 
 
    this->Launch(l, j-1);
    this->Launch(j+1, u);
}
 
int QuickSort4::GetRand(int l, int u)
{
    srand(time(NULL));
    return l + rand() % (u-l + 1);
}
 
unsigned int QuickSort4::getCutoff(void)
{
    return this->cutoff;
}
 
void QuickSort4::setCutoff(unsigned int cutoff)
{
    this->cutoff = cutoff;
}
 
QuickSort4::~QuickSort4(void)
{
}