struct SortResult
{
    Array sortedArray;
    int compareCount;
    int swapCount;
    int timeSort;
    SortResult (Array sortedArray = Array(), int compareCount = 0, int swapCount = 0, int timeSort = 0)
            : sortedArray(sortedArray), compareCount(compareCount), swapCount(swapCount), timeSort(timeSort) {};
    SortResult (const SortResult& o)
            : sortedArray(o.sortedArray), compareCount(o.compareCount), swapCount(o.swapCount), timeSort(o.timeSort) {};
};
class Sort
{
public:
    virtual SortResult sort(const Array& inputArray) {return SortResult();}
};

class ShellSort : public Sort
{
public:
    virtual SortResult sort(const Array& inputArray)
    {
        SortResult res = SortResult(inputArray);
        Array& array = res.sortedArray;
        clock_t t = clock();
        for (int step = array.size() / 2; step > 0; step /= 2)
            for (int i = step; i < array.size(); i++)
            {
                int tmp = array[i];
                int j = i;
                for (; j >= step; j -= step)
                {
                    res.compareCount++;
                    if (tmp < array[j - step])
                    {
                        array[j] = array[j - step];
                        res.swapCount++;
                    }
                    else
                        break;
                }
                array[j] = tmp;
            }
        res.timeSort = clock() - t;
        return res;
    }
};

class BubbleSort : public Sort
{
public:
    virtual SortResult sort (const Array& inputArray)
    {
        SortResult res = SortResult(inputArray);
        Array& array = res.sortedArray;
        clock_t t = clock();
        int flag;
        int tmp;
        do
        {
            flag = 0;
            for(int i = 0; i < array.size() - 1; i++)
            {
                res.compareCount++;
                if(array[i] > array[i + 1])
                {
                    flag = 1;
                    tmp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1]= tmp;
                    res.swapCount++;
                }
            }
        }
        while(flag);
        res.timeSort = clock() - t;
        return res;
    }
};

class SelectSort : public Sort
{
public:
    virtual SortResult sort (const Array& inputArray)
    {
        SortResult res = SortResult(inputArray);
        Array& array = res.sortedArray;
        clock_t t = clock();
        for(int i = 0; i < array.size(); i++)
        {
            int k = i;
            for(int j=i+1; j < array.size(); j++) // цикл выбора наименьшего элемента
            {
                res.compareCount++;
                if (  array[j] < array[k] )
                {
                    k = j; // k - индекс наименьшего элемента
                }
            }
            int tmp = array[k];
            array[k] = array[i];
            array[i] = tmp; // меняем местами наименьший с a[i]
            res.swapCount++;
        }
        res.timeSort = clock() - t;
        return res;
    }
};