# the k-select problem:
# given an unordered sequence of numbers, return the k-smallest value
# a naive solution
# complexity: O(nlogn) (n is the list's length)
# based on sorting the list, therefore performs more work than required
# (sorting the list is equivalent to solving k-select for every 0<=k element
Return the k-th smallest element in the list;
that is, an element in the k-th place in the sorted list
"""
return sorted(L)[k-1]
import random
# a recursive solution
# best case is O(n) - we draw the k-smallest element as the first pivot, by chance
# worst case is O(n^2) - e.g., we want the smallest element (1-select) but we keep drawing the largest element
# turns out average case is O(n) (nontrivial to show)
def select(L, k):
"""
select(list, integer) -> element
Return the k-th smallest element in the list;
that is, an element in the k-th place in the sorted list
"""
n = len(L)
assert 1 <= k <= n
pivot = random.choice(L)
print("L =", L, "; k =", k)
print("pivot =", pivot)
small = [x for x in L if x < pivot]
large = [x for x in L if x > pivot]
# so far same as quicksort
if k <= len(small): # pivot is larger than k-smallest
return select(small, k)
elif k > n - len(large): # pivot is smaller than k-smallest
return select(large, k-(n - len(large)))
else: # pivot is k-smallest
return pivot
# median is a private case of k-select
def median(L):
"""
median(list) -> element
Return the median element in the list; that is, the middle element in the sorted list.
"""
assert L #L not empty
return select(L, (len(L)+1)//2)