Deterministic Selection (Median of Medians) Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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