HW2_qsort_optimize

#include <cstdio>
#include <cstdlib>
#include <ctime>

int * generate(int* n)
{
    int * arr = (int *)malloc((*n) * sizeof(int));
    for (int i = 0; i < *n; ++i)
    {
        arr[i] = rand();
    }
    return arr;
}

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

void inseption_sort(int* a, int n)
{
    int x, j;
    for (int i = 0; i < n; i++)
    {
        x = a[i];
        for (j = i - 1; j >= 0 && a[j] > x; j--)
            a[j + 1] = a[j];
        a[j + 1] = x;
    }
}


int partition(int* a, int r)
{
    int i = 0;

    swap(a[rand() % r], a[r - 1]);

    for (int j = 0; j < r - 1; ++j)
    {
        if (a[j] < a[r - 1] || (a[j] == a[r - 1] && rand() & 1))
        {
            swap(a[i], a[j]);
            i++;
        }
    }

    swap(a[i], a[r - 1]);

    return i;
}

void quick_sort(int* a, int N)
{
    while (N > 1)
    {
        if (N < 40)
        {
            inseption_sort(a, N);
            break;
        }
        int pivot = partition(a, N);
        if (N - pivot > pivot)
        {
            quick_sort(a, pivot);
            a += pivot;
            N -= pivot;
        }
        else
        {
            quick_sort(a + pivot + 1, N - pivot - 1);
            N = pivot;
        }
    }
}
int main()
{
    srand(time(NULL));
    int n = 0, t = 0;
    scanf("%i", &n);
    int* arr = generate(&n);

    if (n > 100)
        quick_sort(arr, n);
    else
        inseption_sort(arr, n);

    for (int i = 1; i < n; i++)
    {
        if (arr[i - 1] > arr[i])
        {
            printf("ERROR %d %d\n", arr[i - 1], arr[i]);
            t++;
        }
    }
    if (!t)
    {
        printf("OK\n");
    }
    return 0;
}