Deterministic Selection (Median of Medians) Algorithm
def merge_tuple(a,b): | |
""" Function to merge two arrays of tuples """ | |
c = [] | |
while len(a) != 0 and len(b) != 0: | |
if a[0][0] < b[0][0]: | |
c.append(a[0]) | |
a.remove(a[0]) | |
else: | |
c.append(b[0]) | |
b.remove(b[0]) | |
if len(a) == 0: | |
c += b | |
else: | |
c += a | |
return c | |
def mergesort_tuple(x): | |
""" Function to sort an array using merge sort algorithm """ | |
if len(x) == 0 or len(x) == 1: | |
return x | |
else: | |
middle = len(x)/2 | |
a = mergesort_tuple(x[:middle]) | |
b = mergesort_tuple(x[middle:]) | |
return merge_tuple(a,b) | |
def lol(x,k): | |
""" Function to divide a list into a list of lists of size k each. """ | |
return [x[i:i+k] for i in range(0,len(x),k)] | |
def preprocess(x): | |
""" Function to assign an index to each element of a list of integers, outputting a list of tuples""" | |
return zip(x,range(len(x))) | |
def partition(x, pivot_index = 0): | |
""" Function to partition an unsorted array around a pivot""" | |
i = 0 | |
if pivot_index !=0: x[0],x[pivot_index] = x[pivot_index],x[0] | |
for j in range(len(x)-1): | |
if x[j+1] < x[0]: | |
x[j+1],x[i+1] = x[i+1],x[j+1] | |
i += 1 | |
x[0],x[i] = x[i],x[0] | |
return x,i | |
def ChoosePivot(x): | |
""" Function to choose pivot element of an unsorted array using 'Median of Medians' method. """ | |
if len(x) <= 5: | |
return mergesort_tuple(x)[middle_index(x)] | |
else: | |
lst = lol(x,5) | |
lst = [mergesort_tuple(el) for el in lst] | |
C = [el[middle_index(el)] for el in lst] | |
return ChoosePivot(C) | |
def DSelect(x,k): | |
""" Function to """ | |
if len(x) == 1: | |
return x[0] | |
else: | |
xpart = partition(x,ChoosePivot(preprocess(x))[1]) | |
x = xpart[0] # partitioned array | |
j = xpart[1] # pivot index | |
if j == k: | |
return x[j] | |
elif j > k: | |
return DSelect(x[:j],k) | |
else: | |
k = k - j - 1 | |
return DSelect(x[(j+1):], k) | |
arr = range(100,0,-1) | |
print DSelect(arr,50) | |
%timeit DSelect(arr,50) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment