import sys ''' This is a simple function to find median of array of five elements It takes 7 comparisons ''' def median_small(arr, left, right): arr[left:right]=sorted(arr[left:right]) return arr[(left+right)//2] # Partition subprocedure def partition(arr, left, right, x): ind=left j=left while ind0 and k<=n): n_by_five=n//5 i=0 i_five=0 med_array=[0]*((n+4)//5) while (i1: pivot_element=nth_order(med_array, 0, i-1, i//2) pivot_pos=partition(arr, left, right, pivot_element) if((pivot_pos-left)==(k-1)): return arr[pivot_pos] elif ((pivot_pos-left)>(k-1)): return nth_order(arr, left, pivot_pos-1, k) else: return nth_order(arr, pivot_pos+1, right, k-pivot_pos+left-1) else: return sys.maxsize def median(arr): n=len(arr) mid=n//2+1 if n==0: raise StatisticsError("no median for empty data") elif (n%2)==1: return nth_order(arr, 0, n-1, mid) else: med_high=nth_order(arr, 0, n-1, mid) #print (med_high) ''' Now, we know that all elements less than 'mid_high' are in range of 0...mid-1. Therefore, the med_low will be largest element in range of 0...mid-2 Which takes n/2-1 comparisons to find the max element ''' med_low=max(arr[0:mid-1]) return (med_low+med_high)/2.0 if __name__=="__main__": testarray=[] if len(sys.argv)==1: testarray=[233,32,3,322,45] print (findmedian(testarray)) print (testarray) elif len(sys.argv)==2: import random testarray=[0]*int(sys.argv[1]) for i in range(len(testarray)): testarray[i]=random.randint(0,1000) print (findmedian(testarray)) print (testarray) else: print ("Invalid arguments")