Created
September 3, 2020 09:43
-
-
Save RaviPabari/8a82cb4dc155984f5b2d8b3fc0a9f5da to your computer and use it in GitHub Desktop.
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
# -*- coding: utf-8 -*- | |
""" | |
Created on Tue Sep 1 12:12:18 2020 | |
@author: Ravi | |
""" | |
''' | |
Deterministic Selection Algorithm !(one of the coolest linear time algo) | |
Running Time O(n) {note that not as practical as randomized, cause the constant here is big compare to randomized} | |
''' | |
import random | |
def partition(x, pivot_index): | |
# i = 0 | |
i = 1 | |
if pivot_index !=0: | |
x[0],x[pivot_index] = x[pivot_index],x[0] | |
for j in range(1,len(x)): | |
if x[j] < x[0]: | |
x[j],x[i] = x[i],x[j] | |
i += 1 | |
x[0],x[i-1] = x[i-1],x[0] | |
return i-1 | |
def find_median(arr): | |
l = sorted(arr) | |
return l[len(l)//2] | |
def splitter(arr): | |
size = 5 | |
return [ arr[i:(i+size)] for i in range(0,len(arr),size)] | |
def choose_pivot(arr): | |
#if there are only 5 elements return median | |
if len(arr)<=5: | |
return find_median(arr) | |
chunks = splitter(arr) | |
sorted_chunks = [sorted(i) for i in chunks] | |
medians = [i[len(i)//2] for i in sorted_chunks] | |
median_of_medians = choose_pivot(medians) | |
return median_of_medians | |
def Dselect(arr,i): | |
if len(arr)==1: | |
return arr[0] | |
pivot = choose_pivot(arr) | |
pivot_index = arr.index(pivot) | |
j = partition(arr,pivot_index) | |
if j==i: | |
return arr[j] | |
if i<j: | |
return Dselect(arr[:j],i) | |
else: | |
return Dselect(arr[j+1:],i-j-1) | |
#use this for testing purpose | |
# arr = [1,2,3,4,5] | |
# arr = random.sample(range(-100,100), 73) | |
# arr = list(range(0,100)) | |
# print('arr =',arr) | |
# print('-'*10) | |
# for i in range(len(arr)): | |
# print(Dselect(arr,i),end=" ") | |
# print(sorted(arr)) | |
# print(Dselect(arr,3)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment