# Quicksort Multiple choice Questions and Answers (MCQs)

## Quicksort Multiple choice Questions and Answers (MCQs)

Congratulations - you have completed Quicksort Multiple choice Questions and Answers (MCQs).

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%

 Question 6 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then
 A T(n) <= 2 T(n/4) + cn B T(n) <= T(n/4) + T(3n/4) + cn C T(n) <= 2 T(3n/4) + cn D T(n) <= T(n/3) + T(3n/4) + cn
Question 6 Explanation:
If there are n/4 elements in one sub-array then T(n/4) comparisons are needed for this sub-array. And T(3n/4) comparison are required for the rest 4n/5 elements, and cn is time required for finding the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4 elements and time complexity will be less than T(n/4) + T(3n/4) + cn.

 Question 7 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require number of comparisons when this algorithm is applied on it?
 A 22 25 56 67 89 B 52 25 76 67 89 C 22 25 76 67 50 D 52 25 89 67 76
Question 7 Explanation:
If the input sequence is already sorted then worst case behaviour occurs for the Quick sort algorithm which use the first element as pivot. Therefore, the input sequence given in 22 25 56 67 89 will require a maximum number of comparisons.

 Question 8 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed to sort 200 elements will be approximately
 A 60.2 sec B 45.54 sec C 31.11 sec D 20 sec
Question 8 Explanation:
The Quick sort requires nlog2n comparisons in best case, where n is size of input array. So, 1000 * log21000 ≈ 9000 comparisons are required to sort 1000 elements, which takes 200 sec. To sort 200 elements minimum of 200 * log2200 ≈ 1400 comparisons are required. This will take 200 * 1400 / 9000 ≈ 31.11 sec.

 Question 9 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Which one of the following sorting algorithm is best suited to sort an array of 1 million elements?
 A Bubble sort B Insertion sort C Merge sort D Quick sort
Crack any exam
Question 9 Explanation:
The Quick sort is best suited to sort the array of 1 million elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst case behaviour and is almost always O(nlogn). And Quick sort requires little additional space and exhibits good cache locality.

 Question 10 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Quick sort is a space-optimised version of .....
 A Bubble sort B Selection sort C Insertion sort D Binary tree sort