Homework-1/qselect.py

16 lines
361 B
Python

import random
def qselect(i, xs):
if xs == []: return None
pivot = xs.pop(random.randrange(len(xs)))
left = [x for x in xs if x < pivot]
right = [x for x in xs if x >= pivot]
if i > len(left) + 1:
return qselect(i - len(left) - 1, right)
elif i == len(left) + 1:
return pivot
else:
return qselect(i, left)