Here is the code for quickselect
def quickSelect(lst, k):
if len(lst) != 0:
pivot = lst[(len(lst)) // 2]
smallerList = []
for i in lst:
if i < pivot:
smallerList.append(i)
largerList = []
for i in lst:
if i > pivot:
largerList.append(i)
count = len(lst) - len(smallerList) - len(largerList)
m = len(smallerList)
if k >= m and k < m + count:
return pivot
print(pivot)
elif m > k:
return quickSelect(smallerList, k)
else:
return quickSelect(largerList, k-m-count)
the issue I am having with it is that it runs with no errors or anything, but when it completes itself I am expecting it to output something to the python shell (in this specific case a median of a list), but I get nothing back. Am I doing something wrong here?
As for what I am inputting for lst and k....
I have tried it with a few different k values as well but to no avail
def quickSelect(lst, k):
if len(lst) != 0:
pivot = lst[(len(lst)) // 2]
smallerList = []
for i in lst:
if i < pivot:
smallerList.append(i)
largerList = []
for i in lst:
if i > pivot:
largerList.append(i)
count = len(lst) - len(smallerList) - len(largerList)
m = len(smallerList)
if k >= m and k < m + count:
return pivot
print(pivot)
elif m > k:
return quickSelect(smallerList, k)
else:
return quickSelect(largerList, k-m-count)
lst = [70, 120, 170, 200]
k = len(lst) // 2
print(quickSelect(lst, k))
produces
>>> 170
The only thing I corrected was the indenting.