[Tutorial 3.1] Quick select duplicate values
The quick select assignment in tutorial 3.1 does not have any tests with duplicate values. These should be made. The following solution should fail:
from typing import List
import random
# Finds the k-th smallest element in the list by using quick select
def quick_select(xs: List[int], k: int) -> int:
pivot = xs[random.randrange(len(xs))]
leftHalf = []
rightHalf = []
for i in xs:
if i < pivot:
leftHalf.append(i)
elif i > pivot:
rightHalf.append(i)
if len(leftHalf)==k-1:
return pivot
if len(leftHalf)>=k:
return quick_select(leftHalf, k)
else:
return quick_select(rightHalf, k-1-len(leftHalf))