Question: c ) Given an array A with elements ( { 8 , 1 , 0 , 9 , 2 , 5 }

c) Given an array A with elements \(\{8,1,0,9,2,5\}\) to be sorted. Suppose your friend rolls a dice to pick the indices of the random pivots to sort the array using the randomized quicksort algorithm. You have the magical powers to decide the number appearing on the roll of the dice your friend is using thereby helping you to decide the order of pivots.
i) Can you use your powers to return the wrong answer by the randomized quicksort? Justify your answer in one line.
ii) What order of pivots will you choose that will make your friend take maximum time to sort the given array. Give two such orders.
iii) Your friend comes to know about your magical powers on his dice and he changes the dice with another fair dice. Let '\( p \)' be the first number you wanted to pick as pivot in part (i). What is the probability that '\( p \)' will be picked as pivot by rolling this new dice?
c ) Given an array A with elements \ ( \ { 8 , 1

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!