QuickSelect finds the kth smallest element of an array in linear time.

quickselect.py

'''
QuickSelect finds the kth smallest element of an array in linear time.
'''

def partition(arr):
    left = []
    right = []

    if not arr:
        return (left, right, None)

    mid = len(arr) // 2
    pivot = arr[mid]

    for x in arr:
        if x > pivot:
            right.append(x)
        elif x < pivot:
            left.append(x)

    return (left, right, pivot)

def quickselect(arr, k):
    left, right, pivot = partition(arr)

    if pivot is None:
        return None

    if len(left) == k - 1:
        result = pivot
    elif len(left) > k - 1:
        result = quickselect(left, k)
    else:
        result = quickselect(right, k - len(left) - 1)

    return result

def test():
    tests = [
        ([1, 2, 3, 4, 5], 3, 3),
        ([9, 8, 7], 2, 8),
        ([-1, 0, 4, 3, 1, 2], 3, 1),
        ([1, 0], 3, None)
    ]

    for arr, k, ans in tests:
        res = quickselect(arr, k)
        assert res == ans, "{} for {} should be {} but got {}".format(arr, k, ans, res)

    print('all ok')

if "__main__" in __name__:
    test()

How is this linear time... you are calling quickselect log(k) time and each time you iternate over the remaining array

@bhuvangu the expected time complexity of this algorithms is O(n). Worst case could be O(n^2)