Matching Nuts and Bolts Problem

Matching Nuts and Bolts Problem.py

Partition(bolts[lo...hi], nut):
  j = lo
  for i in range(lo, hi):
    if bolts[i] < nut:
      swap(bolts[i], bolts[j])
      j += 1
    elif bolts[i] == nut:
      swap(bolts[i], bolts[hi])
      # the bolt that ends up at i might be larger than nut
      i -= 1	
  swap(bolts[j], bolts[hi])
  return j

Similar procedure for partitioning nuts according to a given bolt

Match(nuts[lo...hi], bolts[lo...hi]):
  if lo < hi:
      # choose a nut in [lo...hi] at random
    chosen = nuts[random(lo, hi+1)]
      # partition bolts around the chosen nut
    pivot = Partition(bolts[lo...hi], chosen)
      # partition nuts around the bolt at the pivot position
    Partition(nuts[lo...hi], bolts[pivot])
      # nut and bolt at the pivot position match
      # solve the subproblem [lo...pivot-1] recursively
    Match(nuts[lo...pivot-1], bolts[lo...pivot-1])
      # solve the subproblem [pivot+1...hi] recursively
    Match(nuts[pivot+1...hi], bolts[pivot+1...hi])