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

View Answer

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

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

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

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. What is the average time complexity of randomized quick sort?

a) O(n log n)

b) O(n^{2})

c) O(n^{2} log n)

d) O(n log n^{2})

View Answer

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. Quick sort uses which of the following method to implement sorting?

a) merging

b) partitioning

c) selection

d) exchanging

View Answer

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. Randomized quick sort is an in place sort.

a) true

b) false

View Answer

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. Randomized quick sort is a stable sort.

a) true

b) false

View Answer

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. What is the best case time complexity randomized quick sort?

a) O(log n)

b) O(n log n)

c) O(n^{2})

d) O(n^{2} log n)

View Answer

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. 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^{2}) in any case.

View Answer

Explanation: Randomized quick sort prevents the worst case complexity of O(n

^{2}) in most of the cases. But in some rare cases the time complexity can become O(n

^{2}). 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]); }

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. What is the worst case time complexity of randomized quicksort?

a) O(n)

b) O(n log n)

c) O(n^{2})

d) O(n^{2} log n)

View Answer

Explanation: Randomized quicksort prevents the worst case complexity of O(n

^{2}) in most of the cases. But in some rare cases the time complexity can become O(n

^{2}). The probability of such a case is however very low.

**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__.