Data Structures & Algorithms Multiple Choice Questions on “Quicksort using Median of Three Partitioning”.
1. Quick sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Answer: c
Clarification: 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. What is the median of three techniques in quick sort? Answer: d 3. What is the purpose of using a median of three quick sort over standard quick sort? Answer: a 4. What is the auxiliary space complexity of a median of three quick sort? Answer: c 5. What is the average time complexity of the median of three quick sort? Answer: a 6. Quick sort uses which of the following method to implement sorting? Answer: b 7. Median of three quick sort is an in place sort. Answer: a 8. Median of three quick sort is a stable sort. Answer: b 9. What is the best case time complexity Median of three quick sort? Answer: b 10. Which of the following function chooses a random index as the pivot? b) c) d) Answer: a 11. 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) 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
Clarification: 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).
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
Clarification: 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.
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Clarification: 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.
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
Clarification: 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).
a) merging
b) partitioning
c) selection
d) exchanging
Clarification: Quick sort makes partitions of the input array about the pivot in order to implement sorting. Thus its method of sorting is called partitioning.
a) true
b) false
Clarification: 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).
a) true
b) false
Clarification: 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.
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)
Clarification: 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).
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;
}
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;
}
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;
}
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;
}
Clarification: 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).
a) 8
b) 2
c) 4
d) 9
Answer: a
Clarification: 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.