Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) quickselect, pivot=median of 3, partition=3-way solution in Speedy category for Median by juestr
def checkio(data):
def swap(i, j):
data[i], data[j] = data[j], data[i]
def reorder(i, j):
if data[j] < data[i]:
swap(i, j)
def partition_mo3_3way(left, right):
mid = (left + right) // 2
reorder(left, mid)
reorder(left, right)
reorder(right, mid)
pivot = data[right]
i, j, p = left, left, right
while i < p:
if data[i] < pivot:
swap(i, j)
i += 1
j += 1
elif data[i] == pivot:
p -= 1
swap(i, p)
else:
i += 1
l = min(p - j, right - p + 1)
swap(slice(j, j + l), slice(right - l + 1, right + 1))
return j, j + right - p
def quickselect(k):
left, right = 0, len(data) - 1
while True:
if left == right:
return data[left]
pivot_l, pivot_r = partition_mo3_3way(left, right)
if pivot_l <= k <= pivot_r:
return data[k]
elif k < pivot_l:
right = pivot_l - 1
else:
left = pivot_r + 1
mid, even = divmod(len(data) - 1, 2)
median1 = quickselect(mid)
return (median1 + min(data[mid+1:])) / 2 if even else median1
June 14, 2019
