/*////////////////////////
Lab: Sortings         ////
Name: output console  ////
/*////////////////////////
 
#include "stdafx.h"
#include "stdlib.h"
#include <string>
#include <iostream> 
#include <time.h>
 
using namespace std;
 
int Quicksort(int *arr5, int left, int right, int& shift, int& ask)
{
    register int i, q, j = 0;
    int xx, tmp;
    i = left; q = right;
    xx = arr5[(left + right) / 2];
    do {
        while (arr5[i]<xx && i<right)i++;
        while (xx<arr5[q] && q>left) q--;
 
        if (i <= q)
        {
            ask++;
            tmp = arr5[i];
            arr5[i] = arr5[q];
            arr5[q] = tmp;
            if (arr5[i] < arr5[q])
            {
                shift++;
                //ask--;
            }
            i++;
            q--;
        }
 
 
    } while (i <= q);
    if (left<q) Quicksort(arr5, left, q, shift, ask);
    if (i<right) Quicksort(arr5, i, right, shift, ask);
    return *arr5, shift, ask;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_CTYPE, "Russian");
    int line, column;
    cout << "Введите количество строк от 1 до 15: \n";
lines:
    cin >> line;
    if (line >= 1 && line <= 15)
    {
        cout << endl;
    }
    else
    {
        cout << "Недопустимое значение, введите ещё раз" << endl;
        goto lines;
    }
 
    cout << "Введите количество столбцов от 1 до 15: \n";
columns:
    cin >> column;
 
    if (column >= 1 && column <= 15)
    {
        cout << endl;
    }
    else
    {
        cout << "Недопустимое значение, введите ещё раз" << endl;
        goto columns;
    }
 
    int arr[15][15];
    int arr2[15][15];
    int arr12[15][15];
 
    srand(time(NULL));
    int *arr5 = new int[column];
    cout << "Исходный массив" << endl << endl;
    for (int i = 0; i<line; i++)
    {
        for (int j = 0; j<column; j++)
        {
            arr12[i][j] = arr2[i][j] = arr[i][j] = rand() % 100;
            printf("%4i", arr[i][j]);
        }
        cout << endl;
    }
 
    cout << endl;
    int shift_1 = 0;        //сравнения для пузырька
    int comparison_1 = 0;  //перестановки для пузырька
    printf("Пузырь");
    for (int i = 0; i < line; i++)
    for (int j = 0; j < column - 1; j++)
    for (int k = j + 1; k < column; k++)
    {
        if (abs(arr[i][j]) > abs(arr[i][k]))
        {
            int t;
            t = arr[i][j];
            arr[i][j] = arr[i][k];
            arr[i][k] = t;
            shift_1++;
        }
        comparison_1++;
    }
 
    cout << endl << endl;
    for (int i = 0; i<line; i++)
    {
        for (int j = 0; j<column; j++)
        {
            printf("%4i", arr[i][j]);
        }
        cout << endl;
    }
 
    cout << "\n";
 
    printf("-------------------------------------------------------------\n");
    printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
    printf("-------------------------------------------------------------\n");
    printf("| Bubble           | %19i | %16i |\n", shift_1, comparison_1);
    printf("____________________________________________________________|");
 
    int k = 0, i, j;
    cout << endl << endl << endl;
    cout << "Отбор" << endl << endl;
 
    bool z = 0;
    int shift_2 = 0;
    int comparison_2 = 0;
    for (j = 0; j < line; j++)
    {
        k = 0;
        int H = 0;
        while (k <= column - 1)
        {
            for (i = k + 1; i < column; i++)
            {
                if (abs(arr2[j][i]) < abs(arr2[j][k]))
                {
                    int temp = arr2[j][k];
                    arr2[j][k] = arr2[j][i];
                    arr2[j][i] = temp;
                    H = i;
                    z = 1;
                    shift_2++;  //перестановки
                }
 
                comparison_2++;  //сравнения
            }
            k++;
        }
    }
    for (int i = 0; i<line; i++)
    {
        for (int j = 0; j<column; j++)
        {
            printf("%4i", arr2[i][j]);
        }
        cout << endl;
    }
    cout << endl << endl << endl;
 
    printf("-------------------------------------------------------------\n");
    printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
    printf("-------------------------------------------------------------\n");
    printf("|      Select      | %19i | %16i |\n", shift_2, comparison_2);
    printf("____________________________________________________________|");
 
    cout << endl << endl << endl;
    ///////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////
    /*ВСТАВКА
    ///////////////////////////////////////////////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////////////*/
    cout << "Вставка";
    cout << endl << endl;
    int temp;
    int shift_10 = 0;
    comparison_1 = 0;
    j = 0;
    int *arr3 = new int[column];
    do
    {
        for (int i = 0; i < column; i++)
        {
            arr3[i] = arr[j][i];
        }
 
        int tmp = 0;
        for (int i = 1; i<column; i++)
        {
            temp = arr3[i];
            int W;
            for (W = i - 1; W >= 0 && temp < arr3[W]; W--)
            {
                arr3[W + 1] = arr3[W];
                shift_10++;
 
            }
            arr3[W + 1] = temp;
            comparison_1++;
        }
 
        for (int i = 0; i < column; i++)
        {
            printf("%4i", arr3[i]);
        }
        cout << endl;
        j++;
    } while (j < line);
 
    cout << endl << endl << endl;
 
    printf("-------------------------------------------------------------\n");
    printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
    printf("-------------------------------------------------------------\n");
    printf("|      Insert      | %19i | %16i |\n", shift_10, comparison_1);
    printf("____________________________________________________________|");
    cout << endl << endl;
 
    //////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////
 
 
    //harder, darker, faster
    //nothing but hardcore! 
 
    j = 0;
    cout << "Quicksort" << endl << endl;
    int shift = 0, ask = 0;
    do
    {
        for (int i = 0; i < column; i++)
        {
            arr5[i] = arr12[j][i];
        }
        Quicksort(arr5, 0, column - 1, shift, ask);
        for (int i = 0; i < column; i++)
        {
            printf("%4i", arr5[i]);
        }
        cout << endl;
        j++;
    } while (j < line);
 
    cout << endl << endl;
    printf("-------------------------------------------------------------\n");
    printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
    printf("-------------------------------------------------------------\n");
    printf("|      Quick       | %19i | %16i |\n", shift, ask);
    printf("____________________________________________________________|");
 
    cout << endl << endl << endl;
 
    cout << "Shell" << endl << endl;
    j = 0;
    shift = 0;
    ask = 0;
    int *arr4 = new int[column];
    do
    {
        for (int i = 0; i < column; i++)
        {
            arr4[i] = arr12[j][i];
        }
 
 
        int gap, k;
        int w;
        int temp;
        char a[5] = { 9, 5, 3, 2, 10 };
        for (k = 0; k<5; k++)
        {
            int temp, q = 0;
            int gap = a[k];
            for (i = gap; i<column; i++)
            {
                temp = arr4[i];
                for (q = i - gap; temp < arr4[q] - 1 && q >= 0; q = q - gap)
                {
                    arr4[q + gap] = arr4[q];
                    shift++;
                }
                arr4[q + gap] = temp;
                ask++;
            }
        }
        Quicksort(arr4, 0, column - 1, shift_2, comparison_1);
        for (int i = 0; i < column; i++)
        {
            printf("%4i", arr4[i]);
        }
        cout << endl;
        j++;
    } while (j<line);
 
    cout << endl << endl;
    printf("-------------------------------------------------------------\n");
    printf("| Метод сортировки | Кол-во перестановок | Кол-во сравнений |\n");
    printf("-------------------------------------------------------------\n");
    printf("|      Shell       | %19i | %16i |\n", shift, ask);
    printf("____________________________________________________________|");
 
    cout << endl << endl;
    system("pause");
    return 0;
}