Quicksort using Median of Three Partitioning – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

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(n2)
D) O(n2 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(n2)
C) O(n2 log n)
D) O(n log n2)

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.

Leave a Reply

Your email address will not be published. Required fields are marked *