We consider the implementation of the quick select algorithm quickSelect(a,k) th

ID: 3672205 • Letter: W

Question

We consider the implementation of the quick select algorithm quickSelect(a,k) that finds the kth smallest element
in an array a of size n

Consider the array a shown below.

We wish to find the 5th smallest element (k = 5).

If the element 5 is chosen as the pivot for partitioning which of the following is obtained as a valid partition of the array.

A.[0,2],5,[1,3,7,8,4]

B.[0,2,1,3,4],5,[7,8]

C.[7,8]5[0,2,1,3,4]

D.[0,1,2,3,4],5,[7,8]

Which of the following is obtained as a recursive call following the partitioning.

A.quickSelect([0,2,1,3,4],5)

B.quickSelect([0,2,1,3,4],4)

C.quickSelect([7,8],1)

D.No recursive call

If the pivot were chosen at random, what is the probability that the algorithm terminates without a recursive call?

Write down the answer correct to three decimal places

--> Array 'A' is obtained as a valid partition of the array.

--> 'B' is obtained as a recursive call.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.