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


int main(int argc, char *argv[]) {

	int i, vet[10];

	// Cadastrar vet
	for(i=0; i < 10 ;i++){

		printf("Informe o valor da posicao %i: ", i);
		scanf("%i", &vet[i]);
	}

	printf("\n\nAntes \n");
	// Mostar vet antes
	for(i=0; i < 10 ;i++){

		printf("%i " , vet[i]);
	}

	quickSort(&vet, 0, 9);

	printf("\n\nDepois \n");
	// Mostar vet depois
	for(i=0; i < 10 ;i++){

		printf("%i ", vet[i]);
	}

	return 0;
}

// PARA CONQUISTAR
int particionar(int *vetor, int inicio, int fim) {

	int esq, dir, pivo, aux;

	esq = inicio;
	dir = fim;
	pivo = vetor[inicio];// criterio = primeira posicao do vetor

	while(esq < dir){

		// indo para direita
		while(vetor[esq] <= pivo){
			esq++;
		}
		// indo para esquerda
		while(vetor[dir] > pivo){
			dir--;
		}

		// efetua a troca de posicoes
		if(esq < dir){
			aux = vetor[esq];
			vetor[esq] = vetor[dir];
			vetor[dir] = aux;
		}
	}

	// reposicionando o pivo
	vetor[inicio] = vetor[dir];
	vetor[dir] = pivo;

	return dir;
}

// DIVIDIR
void quickSort(int *vetor, int inicio, int fim) {

	int pivo;

	if(fim > inicio){
		pivo = particionar (vetor, inicio, fim); // divido em duas partes
		quickSort(vetor, inicio, pivo-1); // chamada recursiva
		quickSort(vetor, pivo + 1, fim); // chamada recursiva
	}

}