Quickselect: k-th Smallest in Linear Time

Finding the median or a percentile doesn't need a full sort. Quickselect partitions the list around a pivot like quicksort, but only recurses into the side containing the answer, which takes $O(n)$ on average.

Implement kth_smallest(nums, k) (1-indexed, so k = 1 is the minimum) without sorting the whole list and without heapq. Use the middle element as the pivot, and a three-way partition into < pivot, == pivot and > pivot, so duplicates don't cause slowdowns. Don't modify the input. Raise ValueError if k is out of range.

Then implement percentile(nums, p) using the nearest-rank method: the value at rank $\lceil p/100 \cdot n \rceil$ (minimum rank 1), computed with kth_smallest.