maxim12

#include <stdio.h>
#include <algorithm>
#include <time.h>
#include <stdlib.h>

using namespace std;

void print(int* arr, int n) {
    for (int i = 0; i < n; ++ i)
        printf("%d ", arr[i]);
    printf("\n");
}

/*
a - Проходы
b - Сравнения
c - Перестановки
*/
void quick(int* arr, int n, int* a, int* b, int* c) {
    if (n <= 1)
        return;
    int left = 0;
    int right = n - 1;
    int pivot = (n - 1) >> 1;
    while (left < right) {
        while (left < pivot && arr[left] <= arr[pivot]) {
            ++ left;
            (*b) ++;
        }
        while (right > pivot && arr[right] >= arr[pivot]) {
            -- right;
            (*b) ++;
        }
        (*b) ++;
        if (arr[left] > arr[right]) {
            (*c) ++;
            swap(arr[left], arr[right]);
            if (left == pivot)
                pivot = right;
            else if (right == pivot)
                pivot = left;
        }
    }
    (*a) ++;
    quick(arr, pivot + 1, a, b, c);
    quick(arr + pivot + 1, n - pivot - 1, a, b, c);
}

void radix(int* arr, int n, int* a, int* b, int* c) {
    int d = 1;
    int cnt[10];
    int p[10];
    int *tmp = new int[n];
    int k = 0;

    int mx = 0;
    for (int i = 0; i < n; ++ i)
        if (arr[i] > mx)
            mx = arr[i];
    for (; mx != 0; mx /= 10, ++ k);

    for (int i = 0; i < k; ++ i, d *= 10) { // Проход по разрядам числа

        p[0] = 0;
        fill(cnt, cnt + 10, 0);

        for (int j = 0; j < n; ++ j) { // Подсчёт количества каждой цифры в текущем разряде всех чисел массива
            int x = (arr[j] / d) % 10;
            cnt[x] ++;
        }
        (*a) ++;

        for (int j = 1; j < 10; ++ j) // Устанавливает начальные смещения для сортировки по разряду
            p[j] = p[j - 1] + cnt[j - 1];

        for (int j = 0; j < n; ++ j) { // Сортировка по разряду
            int x = (arr[j] / d) % 10;
            tmp[p[x] ++] = arr[j];
        }
        (*a) ++;

        for (int j = 0; j < n; ++ j) // Запись tmp в arr
            arr[j] = tmp[j];
    }
    delete [] tmp;
}

int main() {
    time_t t = time(NULL);
    printf("t = %d\n", t);
    srand(t);

    int n;
    scanf("%d", &n);
    int* arr = new int[n];
    for (int i = 0; i < n; ++ i)
        arr[i] = rand() % 100 - 50;
    int a = 0, b = 0, c = 0;

    printf("Quick Sort:\n");
    print(arr, n);
    quick(arr, n, &a, &b, &c);
    print(arr, n);
    printf("a = %d, b = %d, c = %d\n", a, b, c);

    a = 0; b = 0; c = 0;
    for (int i = 0; i < n; ++ i)
        arr[i] = rand() % 100;
    printf("\nRadix Sort:\n");
    print(arr, n);
    radix(arr, n, &a, &b, &c);
    print(arr, n);
    printf("a = %d, b = %d, c = %d\n", a, b, c);

    delete [] arr;
    return 0;
}