Quickselect in Python: Find the kth Smallest Element

Python implementation of the Quickselect algorithm to find the kth smallest element in an unsorted list with average O(n) time complexity.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 16 views 0 copies

quickselect selection algorithm sorting

Python code

30 lines
Python 3.9+
Run it 
def quickselect(arr, k):
    """
    Returns the k-th smallest element (0-indexed) using Quickselect.
    Average: O(n), Worst: O(n^2)
    """
    if len(arr) == 1:
        return arr[0]

    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]

    if k < len(left):
        return quickselect(left, k)
    elif k == len(left):
        return pivot
    else:
        return quickselect(right, k - len(left) - 1)


if __name__ == "__main__":
    numbers = [7, 10, 4, 3, 20, 15]
    k = 2  # 0-indexed, so k=2 means the 3rd smallest

    print(f"Array: {numbers}")
    print(f"{k+1}rd smallest element: {quickselect(numbers, k)}")

    # Test multiple k values
    for k in range(len(numbers)):
        print(f"{k+1}th smallest: {quickselect(numbers, k)}")

Output

stdout 
Array: [7, 10, 4, 3, 20, 15]
3rd smallest element: 10
1th smallest: 3
2th smallest: 4
3th smallest: 7
4th smallest: 10
5th smallest: 15
6th smallest: 20

How it works

Quickselect uses a partitioning strategy similar to Quicksort but only recurses into the partition that could contain the kth smallest element. The code chooses the last element as the pivot and builds left (elements ≤ pivot) and right (elements > pivot) lists. By comparing k with the size of left, it decides whether the target is in the left partition, is the pivot itself, or lies in the right partition. This selective recursion yields average O(n) time because each partition step reduces the problem size roughly in half.

Common mistakes

  • Forgetting that k is 0-indexed, so k=2 refers to the third smallest element.
  • Using > instead of >= in the left partition, which breaks stability and yields incorrect results for duplicate values.
  • Neglecting the base case where the array size is 1, leading to infinite recursion.

Variations

  1. Use `random.choice` to select a random pivot to reduce worst-case probability.
  2. Implement an iterative version using a while loop to avoid recursion depth issues on large inputs.

Real-world use cases

  • Finding the median or percentile in large datasets without fully sorting the data.
  • Identifying the top-k or bottom-k records in analytics pipelines for dashboards and reports.
  • Selecting a threshold in statistical algorithms like outlier detection where the kth smallest value defines a cutoff.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes