Problem - Find the kth smallest/largest number in an unsorted array with n element.
Explanation: https://www.youtube.com/watch?v=hGK_5n81drs&ab_channel=BackToBackSWE
Quick select approach: The way that this is done is by using a form of quick sort. It work by a way of partitioning the array into parts.
Lets say we want to find the kth largest number in an array. If the array was sorted we would know what the index of this number would be, it would be (n - k). Since the array isn't sorted we need to find element for the index (n - k).
Now, to find the element we need to implement quick select. Quick select work like this (for finding the largest K):
- First we break the algorithm down to a partition and a selection function.