Explanation
- Quick Select is used to find the **k-th smallest element** in an unordered array. It is similar to QuickSort but only partially sorts the array.
-
-
Steps
- Choose a pivot and partition the array such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
- If the pivot position is the k-th smallest, return it.
- If the pivot position is greater than k, recursively search the left side; otherwise, search the right side.
-
Time Complexity
- O(n) on average, O(n^2) in the worst case.