Quick Select

Use Cases

Use Case	Description	Example
Finding the k-th Smallest Element	Efficiently find the k-th smallest element in an unsorted array without fully sorting it.	For the array `[3, 1, 4, 1, 5, 9]`, the 3rd smallest element is `3`.
Median Finding	Use Quickselect to find the median of an unsorted array.	For the array `[5, 3, 1, 2, 4]`, the median is `3`.
Space-Efficient Selection	Perform selection in O(1) space (in-place) with an average time complexity of O(n).	Useful for large datasets where memory is limited.

Code Template

Partition Function

The partition function rearranges the array such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
The pivot is moved to its correct position in the array.

Partition Logic

Iterate through the array and swap elements smaller than the pivot to the left.
Move the pivot to its final position.

Quickselect Function

The quickselect function recursively partitions the array to find the k-th smallest element.
If the pivot index matches k, return the element at that index.
If k is less than the pivot index, search the left subarray; otherwise, search the right subarray.

def partition(arr, left, right, pivot_index):
    pivot_value = arr[pivot_index]
    arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
    store_index = left

Common Mistakes

Incorrect Pivot Selection

# Wrong: Using a fixed pivot (e.g., always the first element)
pivot_index = left  # Can lead to worst-case O(n^2) performance
# Correct: Use a random pivot
pivot_index = random.randint(left, right)

Incorrect Partition Logic

# Wrong: Not swapping elements correctly
if arr[i] < pivot_value:
    store_index += 1  # Missing swap
# Correct:
if arr[i] < pivot_value:
    arr[store_index], arr[i] = arr[i], arr[store_index]
    store_index += 1

Issues and Considerations

Worst-Case Performance: Quickselect has a worst-case time complexity of O(n^2) if the pivot selection is poor. Using a random pivot mitigates this issue.
Space Complexity: Quickselect uses O(1) space (in-place) but has a O(log n) recursion stack space in the average case.