quickselect

from random import randint


def quick_select(arr: list, k: int) -> int:
    if k < 0:
        raise IndexError("k is less than 0")

    if k > len(arr):
        raise IndexError("k is more than number of elements in array")

    left = 0
    right = len(arr) - 1
    while True:
        rnd = randint(left, right)
        arr[rnd], arr[right] = arr[right], arr[rnd]

        x = arr[right]
        i = left - 1
        for j in range(left, right):
            if arr[j] <= x:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[right] = arr[right], arr[i + 1]
        mid = i + 1

        if mid == k:
            return arr[k]
        elif k < mid:
            right = mid
        else:
            left = mid + 1