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

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

2. 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

3. 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

4. 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

5. What is the average time complexity of the median of three quick sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)
View Answer

6. Quick sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
View Answer

7. Median of three quick sort is an in place sort.
a) true
b) false
View Answer

8. Median of three quick sort is a stable sort.
a) true
b) false
View Answer

9. What is the best case time complexity Median of three quick sort?
a) O(log n)
b) O(n log n)
c) O(n²)
d) O(n² log n)
View Answer

10. 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;
}

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) 8
b) 2
c) 4
d) 9
View Answer

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]