#include <iostream>
#include <string>
#include <clocale>
#include <windows.h>

void output_mas(int *m, int size);

using namespace std;

void sort_vibor(int *m, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int nMin = i;
        for (int j = i + 1; j < size; j++)
            if (m[j] < m[nMin]) nMin = j;
        if (nMin != i)
        {
            int c = m[i];
            m[i] = m[nMin];
            m[nMin] = c;
        }
    }
}

void quickSort(int *m, int nStart, int nEnd)
{
    int L, R, c, X;
    if (nStart >= nEnd)
        return; // готово
    L = nStart;
    R = nEnd;
    X = m[(L + R) / 2]; // или X = A[irand(L,R)];
    while (L <= R)
    {         // разделение
        while (m[L] < X)
            L++;
        while (m[R] > X)
            R--;
        if (L <= R)
        {
            c = m[L];
            m[L] = m[R];
            m[R] = c;
            L++; R--;
        }
    }
    quickSort(m, nStart, R);   // рекурсивные вызовы
    quickSort(m, L, nEnd);
}

void main()
{
    setlocale(LC_ALL, "Russian");
    int per = 0;
    const int n1 = 100;
    const int n2 = 1000;
    const int n3 = 10000;
    int mas1[n1], mas2[n2], mas3[n3];

    for (int i = 0; i < n1; i++)
        mas1[i] = rand() % 50;
    for (int i = 0; i < n2; i++)
        mas2[i] = rand() % 50;
    for (int i = 0; i < n3; i++)
        mas3[i] = rand() % 50;
    cout << "Исходный массив: " << endl;
    output_mas(mas1, n1);

    sort_vibor(mas1, n1);
    cout << "Сортировка выбором: " << endl;
    output_mas(mas1, n1);
    cout << endl;
    cout << "Количество перестановок сортировкой выбора в массиве на 100 элементов=" << per;
    cout << endl;
    per = 0;
    sort_vibor(mas2, n2);
    cout << "Количество перестановок сортировкой выбора в массиве на 1000 элементов=" << per;
    cout << endl;
    per = 0;
    sort_vibor(mas3, n3);
    cout << "Количество перестановок сортировкой выбора в массиве на 10000 элементов=" << per;


    for (int i = 0; i < n1; i++)
        mas1[i] = rand() % 50;
    for (int i = 0; i < n2; i++)
        mas2[i] = rand() % 50;
    for (int i = 0; i < n3; i++)
        mas3[i] = rand() % 50;
    cout << endl;
    cout << "Исходный массив: " << endl;
    output_mas(mas1, n1);
    per = 0;
    quickSort(mas1, 0, n1 - 1);

    cout << "Быстрая сортировка: " << endl;
    output_mas(mas1, n1);
    cout << endl;
    cout << "Количество перестановок ,быстрой сортировкой в массиве на 100 элементов=" << per;
    cout << endl;
    per = 0;
    quickSort(mas2, 0, n2 - 1);
    cout << "Быстрая сортировка: " << endl;
    cout << endl;
    cout << "Количество перестановок ,быстрой сортировкой в массиве на 1000 элементов=" << per;
    cout << endl;
    per = 0;
    quickSort(mas3, 0, n3 - 1);

    cout << "Быстрая сортировка: " << endl;
    cout << endl;
    cout << "Количество перестановок ,быстрой сортировкой в массиве на 10000 элементов=" << per;
    cout << endl;

    cin.get(); cin.get();
}

void output_mas(int *m, int size)
{
    for (int i = 0; i < size; i++)
    {
        if (i % 20 == 0)
            cout << endl;
        cout << m[i] << " ";
    }

    cout << endl;
}