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);
            }
            num++;
        }
    }

                    // 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];

    if (numpivs == 3){
            if (pivs[0] == pivs[1])
                pivs[0] = inds[0];

            if (pivs[1] == pivs[2])
                pivs[2] = inds[6];

            num++; num++;
    }
    num++;

}

int partition(int *u, int piv, int tam){
    int i, j = 0, valpiv = u[piv];
    swap(u, piv, tam-1);

    for (i = 0; i < tam-1; i++){
        if (u[i] < valpiv){
            swap(u, j, i);
            j++;
        }
        num1++;
    }

    swap (u, j, tam-1);
    return j;
}

void Quicksort1(int *v, int tam){
    numchamadas1++;
    int ind;
    int res[1];

    if (tam < 2){
        return; // Casos base
    }
    num1++;
    if (tam == 2){
        if (v[0] > v[1])
            swap(v, 0, 1);
        return;
    }
    num1++;

    num1++;
    if (tam == 3){  // Caso base 3
        num1++;
        if (v[0] > v[1]){
            num1++;
            if (v[0] > v[2]){
                num1++;
                swap(v, 0, 2);
                num1++;
                if (v[0] > v[1])
                    swap (v, 0, 1);
                }
                else
                    swap(v, 0, 1);
                }
            else{
                num1++;
                if (v[0] > v[2]){
                    swap(v, 1, 2);
                    swap(v, 0, 1);
                }
                else{
                    num1++;
                    if (v[1] > v[2])
                        swap(v, 1, 2);
                }
            }
        return;
    }

    pickapivo(v, tam, 1, res);
    // Particionamos
    ind = partition(v, res[0], tam);

    Quicksort1(v, ind);
    Quicksort1(v + ind + 1, tam - ind - 1);
}

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

    int valpivhi = v[indpivhi];
    int valpivlo = v[indpivlo];

    num2++;
    if (indpivlo == n-1){
        swap(v, indpivhi, indpivlo);
        indpivlo = indpivhi;
    }

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

    for (i = 0; i < n-2; i++){
        num2++;
        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++){
        num2++;
        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 tam){
    int res[2];
    numchamadas2++;
    num2++;
    if (tam < 2)
        return; // Casos base

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

    num2++;
    if (tam == 3){  // Caso base 3

        num2++;
        if (v[0] > v[1]){
            num2++;
            if (v[0] > v[2]){
                swap(v, 0, 2);
                num2++;
                if (v[0] > v[1])
                    swap (v, 0, 1);
                }
                else
                    swap(v, 0, 1);
                }
            else{
                num2++;
                if (v[0] > v[2]){
                    swap(v, 1, 2);
                    swap(v, 0, 1);
                }
                else{
                    num2++;
                    if (v[1] > v[2])
                        swap(v, 1, 2);
                }
            }
        return;
    }

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

    int piv2;
    int piv1 = partition2(v, tam, res[0], res[1], &piv2);
    Quicksort2(v, piv2);
    Quicksort2(v + piv2 + 1, piv1-piv2 - 1);
    Quicksort2(v + piv1 + 1, tam -piv1 - 1);
}

void partition3(int *v, int tam, int pivlo, int pivmid, int pivhi, int *res){
    int i, j = 0, indpivlo = pivlo, indpivmid = pivmid, indpivhi = pivhi;
    int valpivlo = v[indpivlo], valpivmid = v[indpivmid], valpivhi = v[indpivhi];

    /* --------- Checagens chatas pra colocar os pivos ----- */
    num3++;
    if(tam - 1  != indpivlo && tam - 1 != indpivmid)
        swap (v, indpivhi, tam-1);
    else{
        num3++;
        if (indpivlo == tam - 1){
            swap (v, indpivlo, indpivhi);
            indpivlo = indpivhi;
        }
        else{
            swap (v, indpivmid, indpivhi);
            indpivmid = indpivhi;
        }
    }
    num3++;
    if (tam - 2 != indpivlo)
        swap (v, indpivmid, tam-2);

    else{
        swap (v, indpivmid, indpivlo);
        indpivlo = indpivmid;
    }

    swap (v, indpivlo, tam-3);

    /* ---------------------------------------------------- */

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

    swap(v, j, tam-3);
    indpivlo = j;

    for (i = j; i < tam-2; i++){
        num3++;
        if (v[i] < valpivmid){
            swap(v, i, j);
            j++;
        }
    }

    swap(v, j, tam-2);
    indpivmid = j;

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

    swap(v, j, tam-1);
    indpivhi = j;

    res[0] = indpivlo; res[1] = indpivmid; res[2] = indpivhi;
}

void Quicksort3(int *v, int tam){
    num3++;
    numchamadas3++;
    printf("tam = %d na chamada %d.\n", tam, numchamadas3);
    if (tam < 2)    // Caso base
        return;

    num3++;
    if (tam == 2){  // Caso base 2
        if (v[0] > v[1])
            swap (v, 0, 1);
            return;
            }
    num3++;
    if (tam == 3){  // Caso base 3
        num3++;
        if (v[0] > v[1]){
            num3++;
            if (v[0] > v[2]){
                swap(v, 0, 2);
                num3++;
                if (v[0] > v[1])
                    swap (v, 0, 1);
                }
                else
                    swap(v, 0, 1);
                }
            else{
                num3++;
                if (v[0] > v[2]){
                    swap(v, 1, 2);
                    swap(v, 0, 1);
                }
                else{
                    num3++;
                    if (v[1] > v[2])
                        swap(v, 1, 2);
                }
            }
        return;
    }

    int res[3];
    int pivs[3];

    pickapivo(v, tam, 3, pivs);

    partition3(v, tam, pivs[0], pivs[1], pivs[2], res);

    Quicksort3(v, res[0]);
    Quicksort3(v + res[0]+1, res[1] - res[0] - 1);
    Quicksort3(v + res[1]+1, res[2] - res[1] - 1 );
    Quicksort3(v + res[2]+1, tam - res[2] - 1);
}