Question

Write a program, using any language you want, that uses a Randomized-Select algorithm. Briefly explain what it does, how it does. Include code and show output.

Answer 1

#As language not specified, using Python, comment if anything else required

#randomisedPartition using partition process of QuickSort()
def randomisedPartition(array, l, r):
   x = array[r]
   i = l
   for j in range(l, r):
       if array[j] <= x:
           array[i], array[j] = array[j], array[i]
           i += 1
   array[i], array[r] = array[r], array[i]
   return i

def randomizedSelect(array, l, r, k):
   #Randomised partition for searching
   index = randomisedPartition(array, l, r)
  
   # if index is the required position then return
   if (index - l == k - 1):
   return array[index]

   # If position is greater then recursion for left subarray
   if (index - l > k - 1):
   return randomizedSelect(array, l, index - 1, k)
   # Else recursion for right subarray
   return randomizedSelect(array, index + 1, r, k - index + l - 1)

array = [ 7, 44, 76, 2, 11, 9, 3, 23, 34, 32, 15, 18 ]
size = len(array)
k = 3
print(k,"rd smallest element is ",randomizedSelect(array, 0, size - 1, k))
k = 9
print(k,"th smallest element is ",randomizedSelect(array, 0, size - 1, k))

Comment down for queries