#include <iostream>

using namespace std;

void init(int* a, int n) {
    for (int i = 0; i < n; ++i)
        a[i] = rand() % n;
}

void print(int* a, int n) {
    int i;
    for (i = 0; i < n - 1; ++i)
        cout << a[i] << " ";
    cout << a[i] << endl;
}

void swap(int& a, int& b) {
    a += b;
    b = a - b;
    a -= b;
}

// 45. Метод поиска с обменом (сортировка посредством выбора)
// Пространственная сложность – О(N)
// Кол-во сравнений – О(N^2)
// Кол-во пересылок – О(N)
void sort_choice(int* a, int n) {
    for (int i = 0; i < n; ++i) {
        int min = a[i], k = i;
        for (int j = i; j < n; ++j)
            if (a[j] < min) {
                min = a[j];
                k = j;
            }
        a[k] = a[i];
        a[i] = min;
    }
}

// 46. Алгоритм «Пузырька»
// Пространственная сложность – О(N)
// Кол-во сравнений и пересылок – О(N^2)
void sort_bubble(int* a, int n) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i - 1; ++j)
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
}

// 47. Челночная сортировка (сортировка вставками)
// Пространственная сложность – О(N)
// Кол-во сравнений и пересылок – О(N^2)
void sort_shake(int* a, int n) {
    for (int i = 0; i < n - 1; ++i)
        if (a[i] > a[i + 1]) {
            swap(a[i], a[i + 1]);
        for (int k = i; a[k] < a[k - 1] && k >= 1; --k)
            swap(a[k], a[k - 1]);
    }
}

// 48. Метод подсчета
// Пространственная сложность – О(N)
// Кол-во сравнений – О(N^2)
// Кол-во пересылок – О(N)
void sort_count(int* a, int n) {
    int* b = new int[n];
    for (int i = 0; i < n; ++i)
        b[i] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j])
                ++b[i];
            else
                ++b[j];
    int* c = new int[n];
    for (int i = 0; i < n; ++i)
        c[b[i]] = a[i];
    for (int i = 0; i < n; ++i)
        a[i] = c[i];
    delete[] c;
    delete[] b;
}


// 49. Метод парных сравнений
// Пространственная сложность – О(N)
// Кол-во сравнений и пересылок – О(N^2)
void sort_pair(int* a, int n) {
    bool flag1 = true, flag2 = true;
    while (flag1 && flag2) {
        flag1 = false;
        for (int i = 0; i < n - 1; i += 2)
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                flag1 = true;
            }
        flag2 = false;
        for (int i = 1; i < n - 1; i += 2)
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                flag2 = true;
            }
    }
}

// 50. Быстрая сортировка
// Временная сложность – О(N*logN)
void hoar_sort(int* a, int left, int right) {
    int i = left, j = right;
    int f = a[left + rand() % (right - left + 1)];
    do {
        while (a[i] < f)
            ++i;
        while (a[j] > f)
            --j;
        if (i <= j) {
            if (i < j)
                swap(a[i], a[j]);
            ++i;
            --j;
        }
    } while (i <= j);
    if (left < j)
        hoar_sort(a, left, j);
    if (right > i)
        hoar_sort(a, i, right);
}

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

    int n;
    cout << "n = ";
    cin >> n;
    cout << endl;
    int* a = new int[n];

    init(a, n);
    print(a, n);
    sort_choice(a, n); // 45. Метод поиска с обменом (сортировка посредством выбора)
    print(a, n);
    cout << endl;

    init(a, n);
    print(a, n);
    sort_bubble(a, n); // 46. Алгоритм «Пузырька»
    print(a, n);
    cout << endl;

    init(a, n);
    print(a, n);
    sort_shake(a, n); // 47. Челночная сортировка (сортировка вставками)
    print(a, n);
    cout << endl;

    init(a, n);
    print(a, n);
    sort_count(a, n); // 48. Метод подсчета
    print(a, n);
    cout << endl;

    init(a, n);
    print(a, n);
    sort_pair(a, n); // 49. Метод парных сравнений
    print(a, n);
    cout << endl;

    init(a, n);
    print(a, n);
    hoar_sort(a, 0, n - 1); // 50. Быстрая сортировка
    print(a, n);
    cout << endl;

    delete[] a;
    system("pause");
    return 0;
}