Quickselect

• Time : O(n)
• Space : O(1)

#include <vector>
using namespace std;
// best O(n) time | O(1) space
// avg O(n) time | O(1) space
// worst O(n^2) time | O(1) space

// prove avg : n + n / 2 + n / 4 + ... and so on
// it means 1 + 2 + 4 + .... n
// and it cames to 2 * n - 1
// so we can judge avg is O(n) witch is divde half in one operation
int dnc(vector<int>& array, int k, int l, int r) {
	if(l == r) return array[l];
	if(l + 1 == r) {
		if(array[l] > array[r]) swap(array[l], array[r]);
		return array[k];
	}
	int pivot = array[r];
	int left = l, right = r - 1;
	while(left <= right) {
		while(left <= right and array[left] < pivot) left++;
		while(left <= right and array[right] > pivot) right--;
		if(left <= right and array[left] > array[right])
			swap(array[left++], array[right--]);
	}
	
	swap(array[left], array[r]);
	if(left == k) return array[k];
	if(left + 1 <= k)
		return dnc(array, k, left + 1, r);
	return dnc(array, k, l, left - 1);
}

int quickselect(vector<int> array, int k) {
  return dnc(array, k - 1, 0, array.size() - 1);
}