void swap(int arr[], int a, int b) {
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void quicksort(int arr[], int lower, int upper) {
	if (lower == upper) { return; }
	int pivot = lower + (rand() % (upper-lower+1));
	swap(arr, pivot, upper);
	pivot = upper;
	int middle = lower;
	for (int i = lower; i < upper; i++) {
		if (arr[i] < arr[pivot]) {
			swap(arr, i, middle);
			middle++;
		}
	}
	swap(arr, pivot, middle);
	if (middle != upper) {
		quicksort(arr, middle+1, upper);
	}
	if (middle != lower) {
		quicksort(arr, lower, middle-1);
	}
}

void quicksort(int arr[], int arrsize) {
	quicksort (arr, 0, arrsize-1);
}