Engineering Questions with Answers - Multiple Choice Questions

# Quicksort using Median of Three Partitioning Multiple Choice MCQ

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

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

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

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)

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)

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

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

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

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)

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;
}```

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