Mastering Algorithms for Problem Solving in Python/

...

/

Linear-Time Selection

Linear-Time Selection

Understand the efficiency and effectiveness of the linear-time selection algorithm.

We'll cover the following...

During our discussion of quick-sort, we claimed in passing that we can find the median of an unsorted array in linear time. The first such algorithm was discovered by Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob Tarjan in the early 1970s. Their algorithm actually solves the more general problem of selecting the kk-th smallest element in an nn-element array, given the array and the integer kk as inputs, by using a variant of an algorithm called quickselect or one-armed quick-sort. Quickselect was first described by Tony Hoare in 1961, literally on the same page where he first published quick-sort.

Quick-select

The generic quickselect algorithm chooses a pivot element, partitions the array using the same partition subroutine as quick-sort, and then recursively searches only one of the two subarrays, specifically the one that contains the kk-th smallest element of the original input array. The pseudocode for quickselect is shown below.

Algorithm

QuickSelect(A[1..n],k):‾if n=1return A[i]elseChoose a pivot element A[p]r←Partition(A[1..n],p)if k<rreturn QuickSelect(A[1..r−1],k)else if k>rreturn QuickSelect(A[r+1..n],k−r)elsereturn A[r]\underline{QuickSelect(A[1 .. n], k):} \\ \hspace{0.4cm} if\space n=1 \\ \hspace{1cm} return\space A[i] \\ \hspace{0.4cm} else \\ \hspace{1cm} Choose\space a\space pivot\space element\space A[p] \\ \hspace{1cm} r ← Partition(A[1 .. n], p) \\ \hspace{1cm} if\space k < r \\ \hspace{1.7cm} return\space QuickSelect(A[1 .. r − 1], k) \\ \hspace{1cm} else\space if\space k > r \\ \hspace{1.7cm} return\space QuickSelect(A[r + 1 .. n], k − r) \\ \hspace{1cm} else \\ \hspace{1.7cm} return\space A[r]

Implementation

Python 3.10.4
def partition(A, p):
    pivot = A[p]
    A[-1], A[p] = A[p], A[-1]
    i = 0
    for j in range(len(A) - 1):
        if A[j] < pivot:
            A[j], A[i] = A[i], A[j]
            i += 1
    A[-1], A[i] = A[i], A[-1]
    return i
def quick_select(A, k):
    if len(A) == 1:
        return A[0]
    p = len(A) // 2
    r = partition(A, p)
    if k < r:
        left_subarray = A[:r]
        return quick_select(left_subarray, k)
    elif k > r:
        right_subarray = A[r + 1 :]
        return quick_select(right_subarray, k - r - 1)
    else:
        return A[r]
A = [10, 5, 2, 0, 7, 6, 4]
k = 3
result = quick_select(A, k - 1)  # k-1 because array indexing starts from 0
print("The " + str(k) + "th smallest element is: " + str(result))

Explanation

  • Lines 1–10: The partition function takes a vector A and an index p as input. It selects a pivot element A[p], moves it to the end of the array, and initializes two pointers i and j. It then scans the array from left to right with j, swapping any element less than the pivot with A[i] and incrementing i. Finally, it swaps the pivot element back to its sorted position, A[i]. The function then returns the index i of the pivot element after it has been sorted.

  • Lines 16–17: We select a pivot index p in the middle of the array and partition the array using the partition function to obtain the pivot element’s sorted index r.

  • Lines 18–20: If k is less than r, it recurses on the left subarray from the beginning of A to r.

  • Lines 21–23: If k is greater than r, it recurses on the right subarray from r + 1 to the end of A.

  • Lines 24–25: If k is equal to r, it returns the pivot element at index r.

This algorithm has two important features. First, just like quick-sort, the correctness of quickselect does not depend on how the pivot is chosen. Second, even if we really only care about selecting medians (the special case k=n/2k = n/2 ...