Quick Select
Quick select often comes up when the question asks for the first/last K elements or the Kth largest/smallest element
Runtime
Best/Average: can guaranteed by shuffling the array
Worst: 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
Easier to implement
def select(start, end):
# Randomly choose a pivot value to guarantee O(n)
random = randint(start, end)
# Swap the pivot value to the end
points[end], points[random] = points[random], points[end]
# Calculate the value of the pivot
pivot_value = calculate(points[end])
idx = start
for i in range(start, end + 1):
# If current value less than pivot, then swap to idx position
if calculate(points[i]) <= pivot_value:
points[i], points[idx] = points[idx], points[i]
idx += 1
return idx - 1
s, e, pos = 0, len(points) - 1, len(points)
while pos != k:
pos = select(s, e)
if pos < k:
s = pos + 1
else:
e = pos - 1
return points[:k]
Last updated