This code is written in Python. The code is incorrect because there may be multiple elements equal to the one we are partitioning around (x) and while the counts lt, eq, gt are computed correctly, the x may not necessarily occur where they should. On paper submit as problem 1, an example where this incorrect code may lead to incorrect result. Also, change the code (don't change the function names etc.) to x this. Your modied code should also run the partitioning in linear time. The code currently does nothing when you input a command.

import random def swap (L,i,j): swap list positions i and j" t = L[i] L[i] = L[j] Lj] = t. def partition (L): n = len (L) idx = random.randrange (n) #put L[idx] into oth position swap (1,0, idx) x = L[O] #lt is number of elements less than L[idx), eg is number of elements equal #gt is number of elements greater than L[idx] (lt, eg, gt) = (0,1,0) (i,j) = (0,1) while (j x: gt = gt+1 j = j + 1 else: if L[j] == x: eg = eg + 1 else: #L[j] (3*n)/4 or gt> (3*n)/4: return false return True def select (L, k): ""return the kth element in L n = len (L) if (n == 0): return None elif (k = n): return None #generate a good partition first (lt, eg, gt, x) = partition (L) while (not good_partition (L, (lt, eg, gt))): (lt, eg, gt, x) = partition (L) if k x: gt = gt+1 j = j + 1 else: if L[j] == x: eg = eg + 1 else: #L[j] (3*n)/4 or gt> (3*n)/4: return false return True def select (L, k): ""return the kth element in L n = len (L) if (n == 0): return None elif (k = n): return None #generate a good partition first (lt, eg, gt, x) = partition (L) while (not good_partition (L, (lt, eg, gt))): (lt, eg, gt, x) = partition (L) if k