Practice: Finding the Median Delivery Time

Nine delivery times and one median, found without sorting the whole list.

Finding a median without sorting is quickselect's most common job, and this exercise practises it: partition a short list by hand, decide which side to keep after each partition, and count how much of the list is ever compared.

A courier records how many minutes each of nine deliveries took: 34 18 52 27 41 23 46 30 38. Find the median with quickselect, using the Lomuto scheme with the last item of the range as the pivot. After each partition, write down the array, the index where the pivot landed, and which side you keep. Then count the comparisons the search made, and name the items it never compared again after the first partition.

Show the answer

The median is 34 minutes, found in three partitions. With nine times, the median is the fifth smallest, the item that belongs at index 4. The trace shows each partition, with low and high around the range still being searched.

Quickselect for the median of nine delivery times

Input34 18 52 27 41 23 46 30 38

Start
1. 34low
2. 18
3. 52
4. 27
5. 41
6. 23
7. 46
8. 30
9. 38high
Nine times, so the median is the fifth smallest, the item that belongs at index 4.
Pivot 38
1. 34low
2. 18
3. 27
4. 23
5. 30
6. 38pivot
7. 46
8. 41
9. 52high
Partitioning around 38 puts it at index 5. Index 4 is to its left, so the median is among the five items before it.
Pivot 30
1. 18low
2. 27
3. 23
4. 30pivot
5. 34high
6. 38
7. 46
8. 41
9. 52
Partitioning indices 0 to 4 around 30 puts it at index 3. Index 4 is now to the right, so the range shrinks to index 4 alone.
Pivot 34
1. 18
2. 27
3. 23
4. 30
5. 34lowhighpivot
6. 38
7. 46
8. 41
9. 52
A range of one item is already in place: 34 sits at index 4, so it is the median.

Result34 minutes

The partitions compared 8, then 4, then 0 items with their pivots, 12 comparisons in all, where comparing every pair of the nine times would take 36. After the first partition, 46, 41 and 52 sat to the right of 38 and were never compared again, and the second partition set aside 18, 27 and 23 the same way. A function that does the search partitions, compares the pivot's index with the target, and keeps one side.

median_delivery.pypy

def partition(items: list[int], low: int, high: int) -> int:
    pivot, i = items[high], low
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i


def quickselect(items: list[int], k: int) -> int:
    low, high, target = 0, len(items) - 1, k - 1
    while True:
        p = partition(items, low, high)
        print(f"pivot {items[p]} lands at index {p}:", " ".join(map(str, items)))
        if p == target:
            return items[p]
        if target < p:
            high = p - 1
        else:
            low = p + 1


minutes = [34, 18, 52, 27, 41, 23, 46, 30, 38]
median = quickselect(list(minutes), (len(minutes) + 1) // 2)
print("median:", median)
print("sorted check:", sorted(minutes)[len(minutes) // 2])

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

pivot 38 lands at index 5: 34 18 27 23 30 38 46 41 52
pivot 30 lands at index 3: 18 27 23 30 34 38 46 41 52
pivot 34 lands at index 4: 18 27 23 30 34 38 46 41 52
median: 34
sorted check: 34

Line 16 stops when the pivot lands on the target index, and line 18 decides which side to keep, the decision the trace made by eye. The last line of output checks the answer against sorting the list and taking the middle item. With an even number of times the median is the mean of the two middle items, which takes a second search, or one search followed by the smallest item to the right of the first answer.

← → move through sections and cards