Engineering Questions with Answers - Multiple Choice Questions

Quicksort using Random Sampling 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

View Answer

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




2 - Question

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

View Answer

Answer: b
Explanation: 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 - Question

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

View Answer

Answer: a
Explanation: 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 - Question

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)

View Answer

Answer: c
Explanation: 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 - Question

What is the average time complexity of randomized quick sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)

View Answer

Answer: a
Explanation: 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 - Question

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

View Answer

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

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

View Answer

Answer: a
Explanation: 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 - Question

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

View Answer

Answer: b
Explanation: 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 - Question

What is the best case time complexity randomized quick sort?
a) O(log n)
b) O(n log n)
c) O(n2)
d) O(n2 log n)

View Answer

Answer: b
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 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(n2) in any case.

View Answer

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




11 - Question

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
Explanation: 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 - Question

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

View Answer

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

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners