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


void swap(int *v, int in, int fi){
    int aux = v[fi];
    v[fi] = v[in]; v[in] = aux;
}

void pickapivo(int *u, int tam, int numpivs, int *pivs){
    int i, j;
    int inds[2 * numpivs + 1], vals[2 * numpivs + 1];

    for (i = 0; i < 2*numpivs + 1; i++){
        inds[i] = rand()%tam;
        vals[i] = u[inds[i]];
    }

    // Agora temos 2 * numpivs + 1 indices aleatorios do vetor. Vamos ordená-los,
    // junto com os seus valores, pra mantermos os índices e valores numa ordem aceitável.

    for (i = 0; i < 2 * numpivs; i++){
        for (j = 0; j < 2*numpivs - i; j++){
            if (vals[j] > vals[j+1]){
                swap (vals, j, j+1);
                swap (inds, j, j+1);
            }
        }
    }

    // Como vals[] e inds[] sofreram as mesmas operacoes de troca, sabemos que os indices
    // em inds[] representam elementos crescentes no vetor. Assim:

    for(i = 0; i < numpivs; i++)
        pivs[i] = inds[2 * i + 1];
}


int partition(int *u, int piv, int l, int r){
    int i = 0, j = 0, indr = l, valpiv = u[piv];

    swap(u, piv, r);

    for (i = l; i < r; i++){
        if (u[i] < valpiv){
            swap(u, indr, i);
            indr++;
        }
    }
    swap (u, indr, r);
    return indr;
}


void quicksort(int *t, int n){
    int i, ind, m = n/2;
    if (n == 1 || n == 0)
        return; // Caso base

    int piv = 0;


    // Particionamos
    ind = partition(t, piv, 0, n-1);

    printf ("Ind = %d!\n", ind);

    quicksort(t, ind + 1);
    quicksort(t + ind + 1, n - ind - 1);
}


int partition2(int v[], int n, int pivlo, int pivhi, int *piv2){
    int cont = 0;
    int i, j = 0;

    int valpivhi = v[pivhi];
    int valpivlo = v[pivlo];

    swap(v, pivhi, n-1); // Tiramos o pivo do caminho
    swap(v, pivlo, n-2);

    for (i = 0; i < n-2; i++){
        if (v[i] < valpivlo){
            swap(v, i, j);
            j++;
        }
    }

    swap(v, j, n-2); // Colocamos o pivo de volta na sua posicao
    *piv2 = j; // Aqui armazenamos o indice do pivo baixo.


    for (i = j; i < n-1; i++){
        if (v[i] < valpivhi){
            swap(v, i, j);
            j++;
        }
    }

    swap (v, j, n-1);

    return j;   // Retornamos entao o indice do fim da segunda particao (primeiro pivo)
}


void quicksort2(int *v, int n){
    int i;
    int res[2];

    if (n < 2)
        return; // Casos base

    if (n == 2){
        if (v[0] > v[1])
            swap(v, 0, 1);
        return;
    }

    pickapivo(v, n, 2, res); // Colocamos os pivos nas posicoes 0 e 1 de res[]

    int piv2;
    int piv1 = partition2(v, n, res[0], res[1], &piv2);


    if (piv2 == piv1)   // Ou seja, os dois pivôs são iguais e estão naturalmente
        piv2++;         // em posições consecutivas, portanto forçamos a partição a prosseguir.

    quicksort2(v, piv1);
    quicksort2(v + piv1, piv2-piv1);
    quicksort2(v + piv2, n-piv2);
}



int main(void) {


    /* --------- Leitura e declaracao de dados ----------*/
    int i, tam;

    printf ("Digite o tamanho do seu vetor, seguido de seus elementos!\n");
    scanf ("%d", &tam);

    int *v = malloc (tam * sizeof(int));

    for (i = 0; i < tam; i++)
        scanf("%d", &(v[i]));
    /* ------------------------------------------------- */

    quicksort2(v, tam);

    printf("Seu vetor, ja ordenadinho e lindjo (LINDAÇO):\n");
    for (i = 0; i < tam; i++)
        printf("%d ", v[i]);

    printf("\nIsso ai­!\n\n");

    return 0;
}