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. Write down an example where this incorrect code may lead to incorrect result. Also, change the code (don't change the function names etc.) to fix this. Your modified code should also run the partitioning in linear time.

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