• Select right as pivot element and left as fill position
  • from left to right move elements smaller or equal to fill position and move the fill position to right
  • Now p is the kth smallest element
def quickselect(l, r):
  pivot = nums[r]
  p = l

  for i in range(l, r):
    if nums[i] <= pivot:
      nums[i], nums[p] = nums[p], nums[i]
      p += 1
  nums[p], nums[r] = nums[r], nums[p]

  if p > k:
    return quickselect(l, p-1)
  elif p < k:
    return quickselect(p+1, r)
    return nums[p]