Definition

Quickselect finds the 'k-th smallest value' in an unsorted array. Like quicksort it partitions around a pivot, but afterwards it keeps narrowing only the side that holds the answer, so it is faster than full sorting.

Key Characteristics

• ✓Does not fully sort - recurses into only one side, achieving average O(n)
• ✓Uses Lomuto partition - picks the last element as pivot and gathers smaller values to the front
• ✓After partition, compares pivot position p with k-1 to proceed into just the left or right side
• ✓In-place - uses only O(1) extra space with no additional array
• ✓Worst case O(n²) but average O(n) - faster than sort-then-index (O(n log n))

Time Complexity