quick-select.py

from typing import List


def quick_select(array: List, start: int, end: int, kth: int):
    if start > end:
        return

    pivot = partition(array, start, end)

    if pivot == kth - 1:
        return array[pivot]
    elif pivot > kth - 1:
        return quick_select(array, start, pivot - 1, kth)
    else:
        return quick_select(array, pivot + 1, end, kth)

      
def partition(array: List, start: int, end: int) -> int:
    pivot = start

    for i in range(start, end):
        if array[i] < array[end]:
            array[i], array[pivot] = array[pivot], array[i]
            pivot += 1

    array[pivot], array[end] = array[end], array[pivot]

    return pivot