private static int partition(int[] array, int start, int end) {
		int randomIdx = new Random().nextInt(end-start+1)+start;
		
		// Switch first item with the one of randomIdx
		int tmp = array[start];
		array[start] = array[randomIdx];
		array[randomIdx] = tmp;
		
		int piovtV = array[start];
		while(start<end) {
			while(start<end && array[end]>=piovtV) {end--;}
			if(start<end) {array[start++] = array[end];}
			while(start<end && array[start]<piovtV) {start++;}
			if(start<end) {array[end--] = array[start];}
		}
		
		array[start] = piovtV;
		return start;
	}