import logging logging.basicConfig(level=logging.DEBUG, format='%(levelname)s - %(message)s') logging.disable(logging.CRITICAL) def quickselect(items, kth, left=None, right=None): # By default, `left` and `right` span the entire range of `items`. if left is None: left = 0 if right is None: right = len(items) - 1 # `right` defaults to the last index in items. if (len(items) == 0) or (not (0 <= kth < len(items))): return None if left == right: return items[left] # BASE CASE logging.debug(f'pivot/leftval={items[left]}, rightval={items[right]} items={items}') # Partition step: i = left for j in range(left + 1, right + 1): logging.debug(f'i={i}, j={j}, left={left}, comparing {items[j]} < {items[left]}') if items[j] < items[left]: i += 1 items[i], items[j] = items[j], items[i] logging.debug(f'i={i}, j={j}, swapped i and j: {items[i]} and {items[j]}, items={items}') # Move the pivot to the correct location: items[i], items[left] = items[left], items[i] # Recursively partition one side only: if kth == i: # We've sorted kth items in `items`. return items[i] # BASE CASE elif i < kth: # TODO We haven't "sorted" enough of `items`, sort items to the right of the pivot. return quickselect(items, kth, i + 1, right) # RECURSIVE CASE else: # We've "sorted" too many return quickselect(items, kth, left, i - 1) # RECURSIVE CASE #a = [6, 0, 2, 16, 14, 10, 18, 20, 12, 4, 8] # kth == i case a = [18, 20, 14, 16, 4, 10, 6, 2, 8, 0, 12] print(a) logging.debug(f'Searching for kth of 3 in {a}') print(quickselect(a, 3)) print(a)