Ksmallest

from random import randint

def median(arr):
    if len(arr) >5:
        raise("Lenth should be less than 5")
    arr = sorted(arr)
    mid, div = divmod(len(arr), 2)
    #print("MiD: ", mid)
    if div == 1:
        return arr[mid]
    return (arr[mid-1]+arr[mid])//2


def runner(y):
    while( len(y) >5):
        rm = []
        for x in range(0, len(y), 5):
            res = median(y[x:min(len(y), x+5)])
            rm.append(res)
        y = list(rm)

    return median(y)


def findKsmallest(arr, k):
    k = k-1
    if(len(arr) <= 5):
        return sorted(arr)

    while( len(arr) > 5):
        m = runner(arr)
        l_arr = []
        r_arr = []

        for i in arr:
            if(i < m):
                l_arr.append(i)
            else:
                r_arr.append(i)

        # print(l_arr, r_arr)

        if (k< len(l_arr)):
            arr = list(l_arr)
        else:
            arr = list(r_arr)
            k = k - len(l_arr)

    return sorted(arr), k


y = list(map(int, input("Enter y values:").split(" ")))
n = int(input("Enter which smallest element:"))
res, h = findKsmallest(y, n)

print("Result: ", res[h])


def test(k, n):
    arr = []
    for x in range(0,k):
        arr.append(randint(1, 500000))

    print("Tested using array of length %d" %len(arr))
    res_arr , h= findKsmallest(arr, n)
    # print("RES ARR:", res_arr)
    print("%dth Smallest: "%n ,res_arr[h])

# test(2000, 3)
# test(2000, 4)
# test(200, 7)
# test(200, 10)
# test(2000, 45)