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

int argMin(int *a, int p, int r) {
    int min, i;

    min = p;
    for (i = p + 1; i <= r; i++)
        if (a[i] < a[min])
            min = i;

    return min;
}

void swap(int *v, int i, int j) {
    int aux;

    aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

int partition(int *v, int p, int r) {
    int x, i, j;

    x = v[r];
    i = p - 1;
    for (j = p; j < r; j++) {
        if (v[j] <= x) {
            i++;
            swap(v, i, j);
        }
    }
    swap(v, i+1, r);
    return i+1;
}

void printArray(int *v, int n) {
    int i;

    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
}

void intercala(int *a, int *b, int p, int q, int r) {
    int i, j, k;

    for (i = p; i <= q; i++)
        b[i] = a[i];
    for (j = q + 1; j <= r; j++)
        b[r + q + 1 - j] = a[j];
    i = p;
    j = r;
    for (k = p; k <= r; k++) {
        if (b[i] <= b[j])
            a[k] = b[i++];
        else
            a[k] = b[j--];
    }
}

void veryQuickSort(int *a, int *b, int p, int r) {
    int m, k, q;

    if (p >= r)
        return;

    k = (p + 2 * r)/3;
    m = argMin(a, k, r);

    swap(a, m, k);

    q = partition(a, p, k);
    veryQuickSort(a, b, p, q-1);
    veryQuickSort(a, b, q+1, k);
    veryQuickSort(a, b, k+1, r);
    intercala(a, b, q, k, r);
}

void quickSort(int *v, int p, int r) {
    int q;

    if (p >=r)
        return;

    q = partition(v, p, r);
    quickSort(v, p, q-1);
    quickSort(v, q+1, r);
}

int main(int argc, char **argv) {
    int *a, *b;
    int i, mod, max;

    if (argc < 2 || (max = atoi(argv[1])) == -1) {
        printf("Forneça o tamanho do vetor.\n");
        exit(1);
    }

    a = malloc(max * sizeof(*a));
    b = malloc(max * sizeof(*b));

    srand(time(NULL));
    mod = max * max * max;
    for (i = 0; i < max; i++) {
        a[i] = rand() % mod;
    }

    printf("Vetor aleatório: ");
    printArray(a, max);

    printf("VeryQuickSort:   ");
    veryQuickSort(a, b, 0, max - 1);
    printArray(a, max);

    printf("QuickSort:       ");
    quickSort(a, 0, max - 1);
    printArray(a, max);

    free(a);
    free(b);
    return 0;
}