Implement Merge Sort and QuickselectStep 4 of 5

Quickselect for top-K

12345

Step 4: Quickselect for top-K

Sorting the whole list to find a single k-th smallest value is wasteful. Quickselect reuses partition but recurses into only ONE side, giving O(n) average time, the standard tool behind median and top-K queries.

Write quickselect(arr, k) that returns the k-th smallest value (0-indexed) of arr. Work on a copy so the caller's list is untouched. Assume 0 <= k < len(arr).

Requirements:

  • Partition a sub-range, look at the returned pivot index p.
  • If p == k you are done. If p < k, the answer is to the right (search p+1..hi). If p > k, search lo..p-1.
  • Keep the same fixed arr[hi] pivot so results are deterministic.
Hints
Starter code
def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result


def merge_sort(arr):
    if len(arr) <= 1:
        return list(arr)
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i


def quick_sort(arr):
    work = list(arr)

    def _qs(lo, hi):
        if lo < hi:
            p = partition(work, lo, hi)
            _qs(lo, p - 1)
            _qs(p + 1, hi)

    _qs(0, len(work) - 1)
    return work


def quickselect(arr, k):
    """Return the k-th smallest (0-indexed) value using partition."""
    # TODO: partition around pivot; recurse only into the side containing k.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step