A python implementation of the quick select algorithm, which is efficient for calculating the value that would appear in the index of a list if it would be sorted, even if it is not already sorted
https://en.wikipedia.org/wiki/Quickselect
"""
def_partition(data, pivot):
"""
Three way partition the data into smaller, equal and greater lists,
in relationship to the pivot
:param data: The data to be sorted (a list)
:param pivot: The value to partition the data on
:return: Three list: smaller, equal and greater
"""
less, equal, greater= [], [], []
forelementindata:
ifelement<pivot:
less.append(element)
elifelement>pivot:
greater.append(element)
else:
equal.append(element)
returnless, equal, greater
defquickSelect(list, k):
#k = len(list) // 2 when trying to find the median (index that value would be when list is sorted)