АИСД Лаба 7

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
void QuickSort(int first, int last);
void ShellSort(int Shell[],int size);
int QuickSortCounter = 0;
int *mas;
void main()
{
    srand(time(0));
    int size, counter = 0;
    cout << "Input array size" << endl;
    while (!(cin >> size) || size > 1000000 || size < 0) {
        cout << "Size must be bigger than 0 and less than 1000000 . Please try one more time." << endl;
        cin.clear();
        while (cin.get() != '\n') continue;
    }
    mas = new int[size];
    int *Shell = new int[size];
    int count = 0;
    cout << "Random array :" << endl;
    for (int i = 0; i < size; i++)
    {
        mas[i] = rand() % 1000000;
        Shell[i] = mas[i];
        cout << mas[i] << " ";
    }

    int first = 0, last = size - 1;
    cout << endl;

    QuickSort(first, last);
    cout << endl << "Sort array :" << endl;
    for (int i = 0; i < size; i++)
    {
        cout << mas[i] << " ";
        if (i + 1 <= size && mas[i] <= mas[i + 1])
            count++;
    }

    cout << endl;
    cout << endl << "QuickSortCounter = " << QuickSortCounter << endl;
    cout << endl;
    ShellSort(Shell, size);

}
void QuickSort(int first, int last)
{
    int change, middle = (last + first) / 2, pivot = mas[middle], premier = first, back = last;
    int min = mas[0],counter = 0, F = 0, L = 0;
    for (int i = premier; i < back; i++) {
        if (mas[i] < min)
            min = mas[i];
    }
    do {
        if (mas[first] >= pivot && mas[last] <= pivot) {
            change = mas[first];
            mas[first] = mas[last];
            mas[last] = change;
            last--;
            if (mas[first] == pivot)
                first--;
        }
        else {
            if (mas[first] >= pivot && mas[last] > pivot)
            {
                last--; first--;
            }
        }

        first++; QuickSortCounter++;
    } while (first < last);

    for (int i = premier; i < back + 1; i++)
    {
        if (counter == 0)
        {
            if (mas[i] > pivot)
            {
                F = i - 1; L = i;
                counter++;
            }
            else {
                if (mas[i] == pivot)
                {
                    F = i; L = i+1;
                    counter++;
                }
            }
        }
    }

    if (F - premier >= 1 || (F - premier == 1 && mas[F] < mas[premier]))
        QuickSort(premier, F);
    if (back - L >= 1 || (back - L == 1 && mas[back] < mas[L]))
        QuickSort(L, back);
}
void ShellSort(int Shell[] ,int size)
{
    int ShellSortCounter = 0;
    int diff = 0, change; int j = 0;

    if (size % 2 == 0)
        diff = size / 2;
    else
        diff = (size - 1) / 2;
    do {
        for (int i = 0; i + diff < size; i++)
        {
            if (Shell[i] > Shell[i + diff])
            {
                change = Shell[i];
                Shell[i] = Shell[i + diff];
                Shell[i + diff] = change;
                ShellSortCounter++;
                j = i;
                while (j - diff >= 0 && Shell[j] < Shell[j - diff])
                {
                    change = Shell[j];
                    Shell[j] = Shell[j - diff];
                    Shell[j - diff] = change;
                    j = j - diff;
                    ShellSortCounter++;
                }
            }
        }
        if (diff % 2 == 0)
            diff = diff / 2;
        else
            diff = (diff - 1) / 2;

    } while (diff >= 1);
    cout << "ShellSortCounter = " << ShellSortCounter << endl;
    cout << endl;
}