Engineering Questions with Answers - Multiple Choice Questions
Quicksort using Median of Three Partitioning MCQ’s
1 - Question
Quick sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
View Answer
Answer: c
Explanation: Quick sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two parts about the pivot and then applies quick sort to both the parts.
2 - Question
What is the median of three techniques in quick sort?
a) quick sort with random partitions
b) quick sort with random choice of pivot
c) choosing median element as pivot
d) choosing median of first, last and middle element as pivot
View Answer
Answer: d
Explanation: In the median of three technique the median of first, last and middle element is chosen as the pivot. It is done so as to avoid the worst case of quick sort in which the time complexity shoots to O(n2).
3 - Question
What is the purpose of using a median of three quick sort over standard quick sort?
a) so as to avoid worst case time complexity
b) so as to avoid worst case space complexity
c) to improve accuracy of output
d) to improve average case time complexity
View Answer
Answer: a
Explanation: Median of three quick sort helps in avoiding the worst case time complexity of O(n2) which occurs in case when the input array is already sorted. However, the average case and best case time complexities remain unaltered.
4 - Question
What is the auxiliary space complexity of a median of three quick sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Answer: c
Explanation: Auxiliary space complexity of median of three quick sort is O(log n) which is used for storing call stack formed due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.
5 - Question
What is the average time complexity of the median of three quick sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
View Answer
Answer: a
Explanation: The average case time complexity of median of three quick sort is the same as that of a standard quick sort as randomized quick sort only helps in preventing the worst case. It is equal to O(n log n).
6 - Question
Quick sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
View Answer
Answer: b
Explanation: Quick sort makes partitions of the input array about the pivot in order to implement sorting. Thus its method of sorting is called partitioning.
7 - Question
Median of three quick sort is an in place sort.
a) true
b) false
View Answer
Answer: a
Explanation: In-place algorithms require constant or very less auxiliary space. Median of three quick sort qualifies as an in-place sorting algorithm. It has a very low auxiliary space requirement of O(log n).
8 - Question
Median of three quick sort is a stable sort.
a) true
b) false
View Answer
Answer: b
Explanation: Median of three quick sort like standard quick sort is also not a stable sorting algorithm. It is because the elements with the same values are not guaranteed to appear in the same relative order in the output sorted array.
9 - Question
What is the best case time complexity Median of three quick sort?
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
View Answer
Answer: b
Explanation: Best case time complexity is given in the case when there is equal partitioning of the array about the pivot. It is given by the relation T(n) = 2T(n/2) + n which gives the result O(n log n).
10 - Question
Which of the following function chooses a random index as the pivot?
a)
int Median(arr, left, right) { int mid; mid = (left + right)/2 if (arr[right] < arr[left]); Swap(arr, left, right); //to swap arr[left],arr[right] if (arr[mid] < arr[left]); Swap(arr, mid, left);//to swap arr[left],arr[mid] if (arr[right] < arr[mid]); Swap(arr, right, mid);// to swap arr[right],arr[mid] return mid; }
b)
int Median(arr, left, right) { int mid; mid = (left + right)/2 if (arr[right] > arr[left]); Swap(arr, left, right); //to swap arr[left],arr[right] if (arr[mid] < arr[left]); Swap(arr, mid, left);//to swap arr[left],arr[mid] if (arr[right] < arr[mid]); Swap(arr, right, mid);// to swap arr[right],arr[mid] return mid; }
c)
int Median(arr, left, right) { int mid; mid = (left + right)/2 if (arr[left] < arr[right]); Swap(arr, left, right); //to swap arr[left],arr[right] if (arr[left] < arr[mid]); Swap(arr, mid, left);//to swap arr[left],arr[mid] if (arr[right] < arr[mid]); Swap(arr, right, mid);// to swap arr[right],arr[mid] return mid; }
d)
int Median(arr, left, right) { int mid; mid = (left + right)/2 if (arr[right] < arr[left]); Swap(arr, left, right); //to swap arr[left],arr[right] if (arr[left] < arr[mid]); Swap(arr, mid, left);//to swap arr[left],arr[mid] if (arr[mid] < arr[right]); Swap(arr, right, mid);// to swap arr[right],arr[mid] return mid; }
View Answer
Answer: a
Explanation: In the median of three quick sort the median of first, last and middle element is chosen. Then the chosen element is taken as a pivot. This helps in avoiding the worst case of O(n2).
11 - Question
What will be the pivot for the array arr={8,2,4,9} for making the first partition when a median of three quick sort is implemented?
a) 8
b) 2
c) 4
d) 9
View Answer
Answer: a
Explanation: While making the first partition the first, last and middle elements will be 8, 9 and 2 respectively. Thus the median element will be 8.