#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)
{
}