250+ TOP MCQs on Quicksort using Random Sampling and Answers

Data Structures & Algorithms Multiple Choice Questions on “Quicksort using Random Sampling”.

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 apply a quick sort to both the parts.

2. What is a randomized quick sort?
a) quick sort with random partitions
b) quick sort with random choice of pivot
c) quick sort with random output
d) quick sort with random input

Answer: b
Clarification: Randomized quick sort chooses a random element as a pivot. It is done so as to avoid the worst case of quick sort in which the input array is already sorted.

3. What is the purpose of using randomized 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
Answer: a
Clarification: Randomized 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. What is the auxiliary space complexity of randomized quick sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: c
Clarification: Auxiliary space complexity of randomized 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. What is the average time complexity of randomized quick sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The average case time complexity of randomized quick sort is same as that of standard quick sort as randomized quick sort only helps in preventing the worst case. It is equal to O(n log n).

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

Answer: b
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.

7. Randomized quick sort is an in place sort.
a) true
b) false

Answer: a
Clarification: In-place algorithms requires constant or very less auxiliary space. Quick sort qualifies as an in place sorting algorithm as it has a very low auxiliary space requirement of O(log n).

8. Randomized quick sort is a stable sort.
a) true
b) false

Answer: b
Clarification: Randomized 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. What is the best case time complexity randomized quick sort?
a) O(log n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: b
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).

10. Which of the following is incorrect about randomized quicksort?
a) it has the same time complexity as standard quick sort
b) it has the same space complexity as standard quick sort
c) it is an in-place sorting algorithm
d) it cannot have a time complexity of O(n²) in any case.

Answer: d
Clarification: Randomized quick sort prevents the worst case complexity of O(n²) in most of the cases. But in some rare cases the time complexity can become O(n²). The probability of such a case is however very low.

11. Which of the following function chooses a random index as pivot.
a)

void partition_random(int arr[], int low, int high) 
{     
    srand(time(NULL)); 
    int random = low + rand() % (high - low); 
    swap(arr[random], arr[high]); 
}

b)

void partition_random(int arr[], int low, int high) 
{    
    srand(time(NULL)); 
    int random = high + rand() % (high - low); 
    swap(arr[random], arr[high]); 
}

c)

void partition_random(int arr[], int low, int high) 
{     
    srand(1); 
    int random = low + rand() % (high - low); 
    swap(arr[random], arr[high]); 
}

d)

void partition_random(int arr[], int low, int high) 
{     
    srand(time(NULL)); 
    int random = low + rand() % (high - low-1); 
    swap(arr[low], arr[high]); 
}

View Answer

Answer: a
Clarification: For generating unique random numbers every time we use srand(time(NULL)). Then after generating the random index we swap the value of element at the random index with the element at last index.

12. What is the worst case time complexity of randomized quicksort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: c
Clarification: Randomized quicksort prevents the worst case complexity of O(n²) in most of the cases. But in some rare cases the time complexity can become O(n²). The probability of such a case is however very low.

& Algorithms.

and Answers.