#include "quicksort.h"
#include <QThread>

QuickSort::QuickSort(QObject *parent):
    IAlgo(parent)
{

}

QString QuickSort::name()
{
    return "Quick Sort";
}

void QuickSort::run()
{
    QVector<int> &data = _data->GetData();
    _run_time = 0;
    sort(data, 0, data.size() - 1);
}

// closed interval
void QuickSort::sort(QVector<int> &data, int left, int right)
{
    if(left >= right){
        return;
    }

    int first_pos = left;
    int last_pos = right;
    int key = data[left];
    while(first_pos < last_pos){
        while(first_pos < last_pos && data[last_pos] > key){
            --last_pos;
            ++_run_time;
        }
        data[first_pos] = data[last_pos];
        _data->Refresh();

        while(first_pos < last_pos && data[first_pos] <= key){
            ++first_pos;
            ++_run_time;
        }
        data[last_pos] = data[first_pos];
        _data->Refresh();
    }
    data[first_pos] = key;
    _data->Refresh();

    sort(data, left, first_pos - 1);
    sort(data, first_pos + 1, right);

    if(_interval > 0){
        QThread::msleep(_interval);
    }
}