Quick Select Algorithm

Quick Select is a variation of the quicksort algorithm. It is an optimized way to find the kth smallest/largest element in an unsorted array.

Algorithm:

• The partition part of the algorithm is same as that of quick sort.
• After the partition function arranges the elements in list according to the pivot and returns the pivot_index, instead of recursing both sides of the pivot index, we recurse only for the part that contains our desired element

Time Complexity Analysis:

Worst case: Worst case occurs when we pick the largest/smallest element as pivot.