Engineering Questions with Answers - Multiple Choice Questions
Quicksort using Random Sampling MCQ’s
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.