Лаб 5.2

/*Алгоритмы
- простого выбора;
- пузырьковая сортировка;
- Хоара.
*/
#include <iostream>
#include <ctime>
#include "windows.h"

using namespace std;

int Init(int *array,  int n)
{
    srand(time(0));     // генерация случайных чисел

    for (int i = 0; i < n; i++)
    {
        array[i] = (rand() % 10);
    }

    return 0;
}

int Print(int *array, int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << array[i] << " ";
    }
    return 0;
}

/*Идея метода состоит в том, чтобы создавать отсортированную последовательность путем
  присоединения к ней одного элемента за другим в правильном порядке.
  Если входная последовательность почти упорядочена, то сравнений будет столько же, значит
  алгоритм ведет себя неестественно.*/

void selectSort(int *array, int n)
{
    int tmp;
    for (int i = 0; i < n; ++i)          // i - номер текущего шага
    {
        int pos = i;
        tmp = array[i];
        for (int j = i + 1; j < n; ++j) // цикл выбора наименьшего элемента
        {
            if (array[j] < tmp)
            {
                pos = j;
                tmp = array[j];
            }
        }
        array[pos] = array[i];
        array[i] = tmp; // меняем местами наименьший с a[i]
    }
}

/*Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву.
По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся
в неправильном порядке, то меняем их местами.*/

void bubbleSort(int *array, int n)
{
    int tmp;

    for (int i = 0; i < n - 1; ++i) // i - номер прохода
    {
        for (int j = 0; j < n - 1; ++j) // внутренний цикл прохода
        {
            if (array[j + 1] < array[j])
            {
                tmp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = tmp;
            }
        }
    }
}


/*Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии)
составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом,
общее быстродействие: O(n log n), что и имеет место на практике.
Итеративный алгоритм быстрой сортировки.

Итеративная QuickSort (массив a, размер size)
{
Положить в стек запрос на сортировку массива от 0 до size-1.
do {
Взять границы lb и ub текущего массива из стека.
do {
1. Произвести операцию разделения над текущим массивом a[lb..ub].
2. Отправить границы большей из получившихся частей в стек.
3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть.
} пока меньшая часть состоит из двух или более элементов
} пока в стеке есть запросы
}
*/

#define MAXSTACK 2048 // максимальный размер стека

void qSortI(int *array, int n)
{

    long i, j; // указатели, участвующие в разделении
    long lb, ub; // границы сортируемого в цикле фрагмента

    long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
                                               // каждый запрос задается парой значений,
                                               // а именно: левой(lbstack) и правой(ubstack)
                                               // границами промежутка
    long stackpos = 1; // текущая позиция стека
    long ppos; // середина массива
    int pivot; // опорный элемент
    int temp;

    lbstack[1] = 0;
    ubstack[1] = n - 1;

    do {
        // Взять границы lb и ub текущего массива из стека.
        lb = lbstack[stackpos];
        ub = ubstack[stackpos];
        stackpos--;

        do {
            // Шаг 1. Разделение по элементу pivot
            ppos = (lb + ub) >> 1;
            i = lb; j = ub; pivot = array[ppos];
            do {
                while (array[i] < pivot) i++;
                while (pivot < array[j]) j--;
                if (i <= j) {
                    temp = array[i]; array[i] = array[j]; array[j] = temp;
                    i++; j--;
                }
            } while (i <= j);

            // Сейчас указатель i указывает на начало правого подмассива,
            // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub.
            // Возможен случай, когда указатель i или j выходит за границу массива

            // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub
            if (i < ppos) { // правая часть больше
                if (i < ub) { // если в ней больше 1 элемента - нужно
                    stackpos++; // сортировать, запрос в стек
                    lbstack[stackpos] = i;
                    ubstack[stackpos] = ub;
                }
                ub = j; // следующая итерация разделения
                        // будет работать с левой частью
            }
            else { // левая часть больше
                if (j > lb) {
                    stackpos++;
                    lbstack[stackpos] = lb;
                    ubstack[stackpos] = j;
                }
                lb = i;
            }
        } while (lb < ub); // пока в меньшей части более 1 элемента
    } while (stackpos != 0); // пока есть запросы в стеке
}



void Error(char c)
{
    std :: cout << "\nТакого алгоритма нет, повторите свой выбор :\n ";
    while (!(std :: cin >> c))     // если ввод не удался, то входим в цикл
    {
        std :: cout << "\nОшибочный ввод! Попытайся еще раз..." << endl;
        std :: cin.clear();           // очистка потока что бы продолжался ввод

                               // считываем элементы в потоке по символу. Удаляем ненужные символы,
                               //  пока символ не равен переводу на новую строку - удаляем его.
        while (std :: cin.get() != '\n');
        {
            std::cout << "Введи значение : ";
        }
    }
}



int main()
{
    setlocale(LC_ALL, "");

    int n;
    char c;
    bool f = true;

    cout << "Введите размер массива : ";
    cin >> n;
    int *array = new int[n];


    do {
    std::cout << "Выберите алгоритм сортировки : \n" << endl;
    std::cout << "1) Сортировка методом протсого выбора " << endl;
    std::cout << "2) Сортировка методом пузырька " << endl;
    std::cout << "3) Сортировка методом Хоара \n" << endl;
    //std::cout << "5) Выход.\n" << endl;


    std :: cout << "Алгоритм №  ";
    std :: cin >> c;

    //cout << "Введи значение " << i << " элемента массива : ";

    switch (c)
    {

    case '1':
        cout << "\n Исходный массив :        ";
        Init(array, n);
        Print(array, n);
        cout << "\n Отсортированный массив : ";
        selectSort(array, n);
        Print(array, n);
        cout << "\n------------------------------------------------------------------------|" << endl;
        break;

    case '2':
        cout << "\n Исходный массив :        ";
        Init(array, n);
        Print(array, n);
        cout << "\n Отсортированный массив : ";
        bubbleSort(array, n);
        Print(array, n);
        cout << "\n------------------------------------------------------------------------|" << endl;
        break;

    case '3':
        cout << "\n Исходный массив :        ";
        Init(array, n);
        Print(array, n);
        cout << "\n Отсортированный массив : ";
        qSortI(array, n);
        Print(array, n);
        cout << "\n------------------------------------------------------------------------|" << endl;
        break;

    default: f = false;
             Error(c);

    }
    //system("cls");
    } while (c ='4');

    std :: cout << endl;

    system("pause");
    return 0;
}