#include "Insert.h";
#include "Select.h";
#include "ShellSortSedj1.h";
#include "QuickSort.h";
#include "BubbleSort.h";
#include "ShakerSort.h";
#include "PyramidSort.h";
 
#include "Timer.h";
#include "RandomGenerator.h";
 
int main()
{
    srand( (unsigned)time(NULL));
 
    // Начальный массив, нужен лишь для инициализации
    int* _x;
 
    // Количество размерностей массивов
    const int sizeNum   = 13;
    int sizes[sizeNum] = 
{10, 50, 100, 400, 800, 1000, 4000, 8000, 10000, 12000, 15000, 18000, 20000};
 
    // Количество видов сортировок
    const int sortTypeNum = 7;
 
    // Инициируем требуемые виды сортировок
    QuickSort      quickSortObj(0, _x);
    PyramidSort    pyramidSortObj(0, _x);
    ShellSortSedj1 shellSortSedj1Obj(10000, _x, 100);    
    ShakerSort     shakerSortObj(0, _x);
    Insert         insertObj(0, _x);
    Select         selectObj(0, _x);
    BubbleSort     bubbleSortObj(0, _x);
 
    // Им будем подсчитывать время
    Timer timerObj(sortTypeNum);
 
    Sort* sorts[sortTypeNum];
    sorts[0] =& quickSortObj;
    sorts[1] =& pyramidSortObj;
    sorts[2] =& shellSortSedj1Obj;
    sorts[3] =& shakerSortObj;
    sorts[4] =& insertObj;
    sorts[5] =& selectObj;
    sorts[6] =& bubbleSortObj;
 
    // Цикл по 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 <iostream>
#include <iomanip>
#include <time.h>
 
using namespace std;
 
class Sort
{
protected:
    int n;
    int* x;
    int swapNum;
    int memEval;
    bool countSwaps;
    char* algName;
 
public:
    Sort(int, int*);
    Sort();
    virtual void Run(void);
    int* getArr(void);
    void setArr(int*);
    int getSize(void);
    void setSize(int);
    int getSwapNum(void);
    void DisableSwapCount(void);
    void CountSwap(void);
    void Print(void);
    void Print2(int*, int);
    void RandomFill(int, int);
    char* getName(void);
    void Swap(int, int);
    void CopyTo(int*);
public:
    ~Sort(void);
};
 

#include "Sort.h"
 
Sort::Sort()
{
    this->setSize(0);
    this->swapNum = 0;
    this->memEval = 0;
}
 
Sort::Sort(int n, int* x)
{
    this->setArr(x);
    this->setSize(n);
    this->swapNum = 0;
    this->memEval = 0;
    this->countSwaps = true;
    this->algName = "Default Sort";
}
void Sort::Run(void) {
 
}
 
int* Sort::getArr(void) {
    return this->x;
}
 
void Sort::setArr(int* x) {
    this->swapNum = 0;
    this->x = x;
}
 
int Sort::getSize(void) {
    return this->n;
}
 
void Sort::setSize(int n) {
    this->n = n;
}
 
char* Sort::getName(void) {
    return this->algName;
}
 
int Sort::getSwapNum(void) {
    return this->swapNum;
}
 
void Sort::DisableSwapCount() {
    this->countSwaps = false;
}
 
void Sort::CountSwap() {
    if (this->countSwaps) {
        this->swapNum++;
    }
}
 
void Sort::Print(void) {
    for (int i = 0; i < this->n; i++) {
        cout << this->x[i] << ' ';
    }
   cout << endl;
}
 
void Sort::RandomFill(int left = 0, int right = 100) {
    srand( (unsigned)time(NULL));
 
    for (int i = 0; i < this->n; i++) {
        this->x[i] = left + rand() % (right - left);
    }
}
 
void Sort::Swap(int i, int j) {
    int tmp;
    tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
    this->CountSwap();
}
 
void Sort::CopyTo(int* dest) {
    for (int i = 0; i < this->n; i++) {
        dest[i] = this->x[i];
    }
}
 
void Sort::Print2(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
   cout << endl;
}
 
Sort::~Sort(void)
{
    delete [] x;
}
 

#pragma once
#include "sort.h"
#include "Insert.h"
 
class QuickSort :
    public Sort
{
protected:
    // Сортировка вставкой, будет им использоваться
    // на конечном этапе
    Insert simpleSortObj;
public:
    QuickSort(int, int*);
    void Run(void);
    void Launch(int*, int);
public:
    ~QuickSort(void);
};
 

#include "QuickSort.h"
 
QuickSort::QuickSort(int n, int* x) : Sort(n, x) {
    this->algName = "Quick Sort [Center]";
}
 
void QuickSort::Run(void)
{
    this->Launch(this->x, this->n);
}
 
void QuickSort::Launch(int* x, int size) {
  long i = 0, j = size - 1; // начальные значения
  int temp, p;
 
  p = x[ size>>1 ];     // выбираем середину
 
  // процедура разделения
  do {
    while (x[i] < p) i++;
    while (x[j] > p) j--;
 
    if (i <= j) {
      temp = x[i]; x[i] = x[j]; x[j] = temp;
      this->CountSwap();
      i++; j--;
    }
  } while (i <= j);
 
 
  // рекурсивные вызовы, если есть, что сортировать 
  if ( j > 0 )    this->Launch(x, j);
  if ( size > i ) this->Launch(x+i, size-i);
}
 
QuickSort::~QuickSort(void)
{
}

#pragma once
#include "sort.h"
 
class PyramidSort :
    public Sort
{
public:
    PyramidSort(int, int*);
    void Run(void);
    void Screening(int, int);
public:
    ~PyramidSort(void);
};

#include "PyramidSort.h"
 
PyramidSort::PyramidSort(int n, int* x) : Sort(n, x) {
    this->algName = "Pyramid Sort";
}
 
void PyramidSort::Screening(int k, int end) {
 
    /* Это чтобы при k=0 и n=0 не делалось лишней
       перестановки*/
    if (0 == end) return;
 
    int tmp;
    int childPos;
    tmp = this->x[k];
 
    while (k <= end/2) {
        childPos = 2*k;  // Левый ребенок элемента k
 
        /* выбираем большего ребенка элемента k
           из 2-х: либо левый, либо правый
           */        
        if (childPos < end && this->x[childPos] < this->x[childPos + 1]) {
            childPos++;
        }
        /* Если родитель x[k] больше всех своих детей,
           то ничего не делаем, он стоит на правильном месте */
        if(tmp >= this->x[childPos]) break;
 
        // иначе - меняем x[k] с наибольшим ребенком
        this->x[k] = this->x[childPos];
        k = childPos;
        this->CountSwap();
    }
    this->x[k] = tmp; this->CountSwap();
}
 
void PyramidSort::Run(void) {
    int i;
    int tmp;
 
    // Построение пирамиды 
    for (i = this->n/2; i >= 0; i--) {
      this->Screening(i, (this->n - 1));
    }
 
    /* Формирование конечной отсортированной
       последовательности + "балансирование"
       пирамиды */
    for (i = this->n - 1; i > 0; i--) {
        // меняем первый с последним 
        this->Swap(0, i);
 
        /* Восстановление баланса 
           для пирамиды x[0..i-1] */
        this->Screening(0, i-1);
    }
}
 
PyramidSort::~PyramidSort(void)
{
}

#pragma once
#include "shellsort.h"
 
class ShellSortSedj1 :
    public ShellSort
{
protected:
    int* dseq;
    int di;
public:
    ShellSortSedj1(int, int*, int = 10, bool = true);
    int GetIncrements(void);
    void Run(void);
    int GetInc(int);
public:
    ~ShellSortSedj1(void);
};