Skip to content

Instantly share code, notes, and snippets.

@isRuslan
Created May 10, 2017 21:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save isRuslan/3a0d69aaeed2bde53a8fd53bbffd5031 to your computer and use it in GitHub Desktop.
Save isRuslan/3a0d69aaeed2bde53a8fd53bbffd5031 to your computer and use it in GitHub Desktop.
QuickSelect finds the kth smallest element of an array in linear time.
'''
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()
@bhuvangu
Copy link

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

@leosabbir
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment