/***** Função menor()
 * Descrição: encontra o menor elemento de um vetor
 * Entrada:     vetor, a e b tal que vetor seja indexado por [a..b]
 * Saída:      o índice do menor elemento
 *****/
int menor(int *v, int a, int b) {
    int menor, i;

    menor = a;
    for (i=a+1;i<=b;i++) {
        if (v[i] < v[menor])
            menor = i;
    }
    return menor;
}

/***** Função troca()
 * Descrição: troca o valor entre duas variaveis inteiras
 * Entrada:     o ponteiro para as duas variáveis a terem valores trocados
 * Saída:      .
 *****/
void troca(int *a, int *b) {
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}

/***** Função selectionSort()
 * Descrição: ordena um vetor por seleção
 * Entrada:     vetor, a e b tal que vetor seja indexado por [a..b]
 * Saída:      .
 *****/
void selectionSort(int *v, int a, int b) {
    int m;

    // condição de parada
    if (a >= b) // tamanho <= 1
        return;

    m = menor(v, a, b);
    troca(&v[a], &v[m]);
    selectionSort(v, a+1, b);
}

/***** Função particiona()
 * Descrição: rearranja os maiores e menores elementos do vetor deixando o pivot no centro
 * Entrada:     vetor, a e b tal que vetor seja indexado por [a..b], e o pivot
 * Saída:      o índice do pivot
 *****/
int particiona(int *v, int a, int b) {
    int i, j;

    // o pivot é sempre o último elemento, v[b]

    i = a-1;

    for (j=a;j<b;j++) {
        if (v[j] <= v[b]) {
            i++;
            troca(&v[j], &v[i]);
        }
    }
    // coloca o pivot no centro
    i++;
    troca(&v[i], &v[b]);

    return i;
}

/***** Função quickSort()
 * Descrição: ordena um vetor por quickSort
 * Entrada:     vetor, a e b tal que vetor seja indexado por [a..b]
 * Saída:      .
 *****/
void quickSort(int *v, int a, int b) {
    int p;

    // condição de parada
    if (a >= b)
        return;

    p = particiona(v, a, b);

    quickSort(v, a, p-1);
    quickSort(v, p+1, b);
}