Advertisement
nathanwailes

QuickSelect

May 18th, 2024
817
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.67 KB | None | 0 0
  1. import random
  2.  
  3. def quickselect(arr, k):
  4.     """
  5.    Returns the k-th smallest element of list within arr.
  6.    """
  7.     if len(arr) == 1:
  8.         return arr[0]
  9.  
  10.     pivot = random.choice(arr)
  11.  
  12.     lows = [el for el in arr if el < pivot]
  13.     highs = [el for el in arr if el > pivot]
  14.     pivots = [el for el in arr if el == pivot]
  15.  
  16.     if k < len(lows):
  17.         return quickselect(lows, k)
  18.     elif k < len(lows) + len(pivots):
  19.         return pivots[0]
  20.     else:
  21.         return quickselect(highs, k - len(lows) - len(pivots))
  22.  
  23. # Example usage:
  24. arr = [3, 2, 1, 5, 4]
  25. k = 2  # looking for the 3rd smallest element, index 2
  26. print(quickselect(arr, k))  # Output: 3
  27.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement