Quickselect (k-th Smallest)

DSA · Classic Algorithms

Theory

Quickselect finds the k-th smallest element in an unsorted array without sorting the whole array. It uses the same partition step as Quick Sort: choose a pivot, move smaller elements to its left and larger ones to its right, so the pivot ends up in its final sorted position. If that position equals k, you are done; if k is smaller, you only need to continue in the left part, otherwise in the right part. Because it recurses into just one side, the average running time is O(n) instead of O(n log n) for sorting. The worst case is O(n^2) with consistently bad pivots, which a random pivot makes very unlikely. It is the standard way to find medians and percentiles.

Why we use it

Finding the median, the k-th largest score or a percentile is common in analytics and interviews, and Quickselect does it in linear time on average.

When to use it

Use it for a single order statistic on a large unsorted array. Use a heap when you need the top k items, or sorting when you need everything in order.

How it works

  1. Choose a random pivot
  2. Partition around it; pivot lands at index p
  3. p == k? Yes: Return arr[p]. No: Choose a side.
  4. k < p? Yes: Search left part. No: Search right part.
  5. Average O(n)

Syntax

partition around pivot -> index p
if p == k: return a[p]
if k < p: search left else search right
Average O(n), worst O(n^2)

Example

import random

def quickselect(nums, k):
    """Return the k-th smallest (0-based)."""
    nums = nums[:]
    lo, hi = 0, len(nums) - 1
    while True:
        pivot_index = random.randint(lo, hi)
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]
        pivot, store = nums[hi], lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        if store == k:
            return nums[store]
        if k < store:
            hi = store - 1
        else:
            lo = store + 1

salaries = [72000, 45000, 98000, 61000, 120000, 53000, 87000]
print("Smallest:", quickselect(salaries, 0))
print("Median:", quickselect(salaries, len(salaries) // 2))
print("2nd highest:", quickselect(salaries, len(salaries) - 2))
print("Check with sort:", sorted(salaries))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic