class QS {
	public static void main(String[] args) {
		int[] arr = randomArray(100);
		print(arr);
		quicksort(arr, 0, arr.length - 1);
		print(arr);
		//System.out.println(check(arr));
	}

	static void quicksort(int[] s, int left, int right) {
		if ( left < right ) {
			int pivotIndex = (int)(Math.random() * (right - left)) + left + 1; //make random number from left to right
			int newPivotIndex = partition(s, left, right, pivotIndex);

			quicksort(s, left, newPivotIndex - 1);
			quicksort(s, newPivotIndex + 1, right);
		}
	}

	static int partition(int[] s, int left, int right, int pivotIndex) {
		int pivot = s[pivotIndex];
		swap(s, pivotIndex, right);

		int storeIndex = left;
		for (int i = left; i < right ; i++) {
			if ( s[i] <= pivot ) {
				swap(s, i, storeIndex);
				storeIndex++;
			}
		}

		//put pivot back
		swap(s, storeIndex, right);
		return storeIndex;
	}

	static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	static int[] randomArray(int n) {
		int[] arr = new int[ n ];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int)(Math.random() * n) + 1;
		}

		return arr;
	}

	static boolean check(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			if ( arr[i] > arr[i+1] ) {
				return false;
			}
		}
		return true;
	}

	static void print(int[] arr) {
		for (int i = 0; i < arr.length ;i++) {
			System.out.print(arr[i] + " ");
		}System.out.println();
	}
}