import java.util.Arrays;

public class QuickSort {

	private void quicksort(int[] valores, int i, int f) {
		if (i < f) {
			int q = partition(valores, i, f);
			quicksort(valores, i, q - 1);
			quicksort(valores, q + 1, f);
		}
	}
	
	private int partition(int[] valores, int i, int f) {
		int pivo = valores[f];
		int baixo = i - 1;
		for (int alto = i; alto < f; alto++) {
			if (valores[alto] <= pivo) {
				troca(valores, ++baixo, alto);
			}
		}
		troca(valores, ++baixo, f);

		return baixo;
	}
	
	private void troca(int[] A, int i, int j){
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
	
	public static void main( String ... args ){
		
		int[] valores = {5, 3, 7, 1, 9, 2, 8, 4};
		
		QuickSort quick = new QuickSort();
		quick.quicksort(valores, 0, 7);
		
		System.out.println( Arrays.toString(valores) );
		
	}
	
}
