16 lines
361 B
Python
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)
|