This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Quicksort using Median of Three Partitioning”.

**1. Quicksort uses which of the following method to implement sorting?**

A) merging**B) partitioning**

C) selection

D) exchanging**Explanation:** In order to implement sorting, Fast Sort divides the input array around the pivot. Partitioning is the name given to this type of sorting.

**2. Median of three quick sort is an in place sort.****A) true**

B) false**Explanation:** Algorithms that run in place need no or very little auxiliary space. An in-place sorting algorithm is defined as the median of three fast sorts. It only needs O square feet of auxiliary space (log n).

**3. Median of three quick sort is a stable sort.**

A) true**B) false****Explanation**: Standard fast sort, like median of three quick sort, is not a stable sorting algorithm. It’s because elements with the same values in the output sorted array aren’t guaranteed to appear in the same relative order.

**4. What is the best case time complexity Median of three quick sort?**

A) O(log n)**B) O(n log n)**

C) O(n^{2})

D) O(n^{2} log n)**Explanation: **When the array is partitioned evenly around the pivot, the best case time complexity is given. It’s calculated using the formula T(n) = 2T(n/2) + n, which yields the result O. (n log n).

**5. 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:** The median of the first, last, and middle element is chosen in the median of three fast form. The selected element is then used as a pivot. This assists in preventing the worst-case scenario of O (n2).

**6. 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**Explanation:** The first, last, and middle elements of the first partition will be 8, 9, and 2 respectively. As a result, the median factor will be eight.

**7. Quick sort uses which of the following algorithm to implement sorting?**

A) backtracking

B) greedy algorithm**C) divide and conquer**

D) dynamic programming**Explanation:** In order to sort a given number, fast sort employs the divide and conquer technique. It divides the array into two sections around the pivot and then sorts both parts quickly.

**8. 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: **The pivot in the median of three-technique is the median of the first, last, and middle elements. It’s done this way to prevent the worst-case scenario of fast sorting, in which the time complexity skyrockets to O. (n2).

**9. 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:** When the input array is already sorted, the median of three fast sort helps to escape the worst-case time complexity of O(n2). The average case and best case time complexities, on the other hand, remain unchanged.

**10. 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: **The median of three fast sort’s auxiliary space complexity is O(log n), which is used to store the call stack generated by recursion. Since the value of log n is similar to 1, algorithms with a space complexity of O(log n) qualify as in place algorithms.

**11. What is the average time complexity of the median of three quick sort?****A) O(n log n)**

B) O(n^{2})

C) O(n^{2} log n)

D) O(n log n^{2})**Explanation:** Since randomised quick sort only helps in avoiding the worst case, the average case time complexity of the median of three quick sort is the same as that of a regular quick sort. It is the same as O. (n log n).

In other words, the median of medians is an approximate median-selection algorithm that produces good pivot elements and aids in the construction of an asymptotically optimal, exact general selection algorithm (especially in terms of worst-case complexity). It is the same as O. (n log n). Fast Sort is a widely used sorting algorithm in computer science. Fast Sort employs a divide-and-conquer strategy. It makes two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, then sorts the sub arrays recursively.