#include <stdio.h>

//pior caso \theta(n²)
//eficiencia media \theta(nlog(n))
int partition(int *A, int p, int r){
	//escolher o pivot(vai ser o ultimo, pois fica mais facil de implementar
	//caso queira escolher um pivo aleatório, basta trocar A[pos_aleatoria] com A[r]
	int pivot = A[r];
	int pos_pivot = p;
	for(int i=p; i < r; ++i){
		if(A[i] <= pivot){
			int aux = A[i];
			A[i] = A[pos_pivot];
			A[pos_pivot] = aux;

			pos_pivot++;
		}
	}
	int aux = A[pos_pivot];
	A[pos_pivot] = pivot;
	A[r] = aux;

	return pos_pivot;
}

int quicksort(int *A, int p, int r){
	printf("p: %d, r: %d\n", p, r);
	if(p < r){
		int q = partition(A, p, r);
		quicksort(A, p, q-1);
		quicksort(A, q+1, r);
	}
}


int main(){
	// pp = 0
	// 13 32 52 69 420 22 42
	int A[7] = {42, 32, 52, 69, 420, 22, 13};
	quicksort(A, 0, 6);
	for(int i=0; i<7; ++i){
		printf("%d ", A[i]);
	}
	printf("\n");
	return 0;
}