## Summary

**Quick Select** is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized `O(n)`

time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have `O(n)`

worst case performance.

**Quick Sort** is an unstable sort. It has amortized `O(nlogn)`

and worst case `O(n^2)`

complexity. Introsort combines Quick Sort and Heap Sort and is guaranteed to have `O(nlogn)`

worst case performance.

A handy template function in the standard library is shown blow.

```
template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
// iterator before nth has smaller or equal value; iterator after nth has larger or equal value
// nth_element(nums.begin(), nums.begin()+k-1, nums.end())
// nums[k-1] will be the kth smallest number.
```

If we want to use the pivot and divide and conquer technique to implement both Quick Select and Sort. Common techniques to avoid infinite loop or wrong answers are listed below.

- Choose left as the pivot;
- loop while left < right (not <=);
- Move right pointer first;
- Decrease right only if left is still < right;

## Quick Select

```
int quick_select(int left, int right, int k, vector<int>& nums) {
int pivot = left;
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[pivot]) {
j--;
}
while (i < j && nums[i] <= nums[pivot]) {
i++;
}
if (i == j) {
break;
}
swap(nums[i], nums[j]);
j--;
}
swap(nums[pivot], nums[i]);
if (i - pivot + 1 == k) {
return nums[i];
} else if (i - pivot + 1 > k) {
return quick_select(left, i - 1, k, nums);
} else {
return quick_select(i + 1, right, k - (i - pivot + 1), nums);
}
}
```

This implementation has the following complexity.

- amortized
`O(n)`

- worst case
`O(n^2)`

(given an array with all same values and`k==n`

; in this case, each time the array only shrinks by one element)

## Quick Sort

```
void quick_sort(int left, int right, vector<int>& nums) {
if (left >= right) {
return;
}
int pivot = left;
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= nums[pivot]) {
j--;
}
while (i < j && nums[i] <= nums[pivot]) {
i++;
}
if (i == j) {
break;
}
swap(nums[i], nums[j]);
j--;
}
swap(nums[pivot], nums[i]);
quick_sort(left, i - 1, nums);
quick_sort(i + 1, right, nums);
}
```

This implementation has the following complexity.

- amortized
`O(nlogn)`

- worst case
`O(n^2)`

(given an sorted array; in this case, each time the array only shrinks by one element)