Randomized Selection Algorithm (Quickselect) – Python Code

Find the kth 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.

Animated visualization of the randomized selection algorithm selecting the 22nd
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]
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)
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),
view raw RSelect.py hosted with ❤ by GitHub


Related Posts
Quick Sort Python Code
Computing Work Done (Total Pivot Comparisons) by Quick Sort