Quick Select

Quick select often comes up when the question asks for the first/last K elements or the Kth largest/smallest element

Runtime

T(n)=T(n2)+O(n)T(n) = T(\frac{n}{2}) + O(n)
  • Best/Average:
    O(n)O(n)
    can guaranteed by shuffling the array
  • Worst:
    O(n2)O(n^2)
    if sorted

Techniques

Kth Element

Arrange largest elements in front by inverting the pivot comparison. This is a common problem type that tests if you know exactly how the partitioning algorithm works.

Partitioning Algorithms

Pick a pivot, partition elements smaller than the pivot to the left, and elements larger to the right of the pivot
Lomuto
Hoare
idx-1 is the pivot index after performing the partitioning the array. Think of idx as the position for the next element that is smaller than the pivot value
  • Easier to implement
1
def select(start, end):
2
# Randomly choose a pivot value to guarantee O(n)
3
random = randint(start, end)
4
# Swap the pivot value to the end
5
points[end], points[random] = points[random], points[end]
6
# Calculate the value of the pivot
7
pivot_value = calculate(points[end])
8
idx = start
9
for i in range(start, end + 1):
10
# If current value less than pivot, then swap to idx position
11
if calculate(points[i]) <= pivot_value:
12
points[i], points[idx] = points[idx], points[i]
13
idx += 1
14
return idx - 1
15
16
s, e, pos = 0, len(points) - 1, len(points)
17
while pos != k:
18
pos = select(s, e)
19
if pos < k:
20
s = pos + 1
21
else:
22
e = pos - 1
23
return points[:k]
Choose first element as pivot
  • Faster in theory
Two pointers, find 2 elements where arr[left] > pivot and arr[right] < pivot, swap and continue. When pointers converge, they converge at where the pivot should be so swap arr[start] and arr[left].
1
partition(start, end):
2
i, j = start, end + 1
3
while True:
4
while i < end and arr[i] < arr[start]:
5
i += 1
6
while j > start and arr[i] > arr[start]:
7
j -= 1
8
if i >= j:
9
break
10
swap(arr[i], arr[j])
11
swap(arr[start], arr[j])
12
return j