I have small python code that implements the quickselect discussed here.
import random
def Quickselect(A, k):
if not A:
return
pivot = random.choice(A)
i = 0
A1 = []
A2 = [] # Two new arrays A1, A2 to store the split lists
for i in range(len(A)):
if A[i] < pivot :
A1.append(A[i])
else:
A2.append(A[i])
if k < len(A1):
return Quickselect(A1, k)
if k > len(A) - len(A2):
return Quickselect(A2, k-(len(A) - len(A2)))
else:
return pivot
pass
def main():
A = [45,1,27,56,12,56,88]
print(Quickselect(A,2))
pass
I seem to be getting an randrange error. Is something amiss?
Edit: Implemented random.choice
instead of random.randint
.
The above code seems to work fine. Thanks to User Blender.
Your error occurs because randrange
breaks when the range is empty (i.e. randrange(1, 1)
).
Use random.choice
instead and change k <= len(A1)
to k < len(A1)
:
def quick_select(A, k):
pivot = random.choice(A)
A1 = []
A2 = []
for i in A:
if i < pivot:
A1.append(i)
elif i > pivot:
A2.append(i)
else:
pass # Do nothing
if k <= len(A1):
return Quickselect(A1, k)
elif k > len(A) - len(A2):
return Quickselect(A2, k - (len(A) - len(A2)))
else:
return pivot