from partition import partition
from random import randrange

def select2(A, p, q, i):
    n = q - p + 1
    if n==1: return A[p]
    loc = randrange(p,q) # choose random integer in [p,q)
    r = partition(A,p,q,loc) # See quicksort slides
    k = r - p 
    if (k == i): return A[r]
    if (i < k):
        return select2(A,p,r-1,i)
    else:
        return select2(A,r+1,q,i-k-1)

if __name__ == "__main__":
    from random import choices

    n=11

    A = choices(range(0,100),k=n)
    print("A=",A);

    median = select2(A,0,n-1,n//2)
    print("median=",median)

    B=sorted(A)
    print("median via sorting = ",B[n//2])