Question

Assume that you run quicksort on n≥7 elements. What is the probability that the 5th and 7th smallest elements are compared?

1) 0

2) 1/4

3) 1/3

4) 1/2

5) 2/3

6) 3/4

7) 1

Assume that you run quicksort on 3 elements. What is the average number of comparisons?

1) 2

2) 9/4

3) 7/3

4) 5/2

5) 8/3

6) 11/4

7) 3

Answer 1

In the first case we want to calculate the probability of 5th and 7th smallest number to get compared . This would be possible only if they are on the same side and one of them becomes a pivot. But they would get separated if 6th smallest element becomes a pivot. Therefore total favourable conditions = 2 , unfavorable conditions = 1 .Total condition is 3. Hence probability = ​​​​​​​2/3

Running quicksort for three elements , three cases possible

case 1. Smallest element gets selected . Two comparisons and two elements are on the right side . Now one more comparison between them . Total comparison is 3

Case 2. Largest element is selected . 2 comparison in the starting and then all the elements come on left side and there is one more comparison between them . Total comparison is 3

Case 3. Middle element is selected . First two comparisons take place . Now elements are on either side . Therefore no other comparison possible. Total comparison is 2

Average =(3+3+2)/3 = ​​​​​​​8/3