Randomized Selection

Find the k^th smallest element in an array without sorting.

That’s basically what this algorithm does. It piggybacks on the partition subroutine from the Quick Sort. If you don’t know what that is, you can check out more about the Quick Sort algorithm here and here, and understand the usefulness of partitioning an unsorted array around a pivot.

Selecting_quickselect_frames — Animated visualization of the randomized selection algorithm selecting the 22^nd smallest value

Python Implementation

	from random import randrange

	def partition(x, pivot_index = 0):
	i = 0
	if pivot_index !=0: x[0],x[pivot_index] = x[pivot_index],x[0]
	for j in range(len(x)-1):
	if x[j+1] < x[0]:
	x[j+1],x[i+1] = x[i+1],x[j+1]
	i += 1
	x[0],x[i] = x[i],x[0]
	return x,i

	def RSelect(x,k):
	if len(x) == 1:
	return x[0]
	else:
	xpart = partition(x,randrange(len(x)))
	x = xpart[0] # partitioned array
	j = xpart[1] # pivot index
	if j == k:
	return x[j]
	elif j > k:
	return RSelect(x[:j],k)
	else:
	k = k - j - 1
	return RSelect(x[(j+1):], k)

	x = [3,1,8,4,7,9]
	for i in range(len(x)):
	print RSelect(x,i),