Quicksort using Random Sampling – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

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 method to implement sorting?
A) merging
B) partitioning
C) selection
D) exchanging

Explanation: In order to implement sorting, Fast Sort divides the input array around the pivot. Partitioning is the name given to this type of sorting.




2. Randomized quick sort is an in place sort.
A) true
B) false

Explanation: Algorithms that run in place need no or very little auxiliary space. Quick sort is classified as an in-place sorting algorithm because it needs only O bytes of auxiliary space (log n).

3. Randomized quick sort is a stable sort.
A) true
B) false

Explanation: Like regular fast sort, randomised quick sort is not a stable sorting algorithm. It’s because elements with the same values in the output sorted array aren’t guaranteed to appear in the same relative order.

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

Explanation: When the array is partitioned evenly around the pivot, the best case time complexity is given. It’s calculated using the formula T(n) = 2T(n/2) + n, which yields the result O. (n log n).

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

Explanation: In most cases, randomised simple sort avoids the worst-case complexity of O(n2). However, in a few rare cases, the time complexity will exceed O. (n2). However, the chances of this happening are extremely slim.




6. 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: We use srand(time(NULL)) to generate unique random numbers each time. After that, we swap the value of the element at the random index with the value of the element at the last index.

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

Explanation: In most cases, randomised quicksort avoids the worst-case complexity of O(n2). However, in a few rare cases, the time complexity will exceed O. (n2). However, the chances of this happening are extremely slim.




8. Quick sort uses which of the following algorithm to implement sorting?
A) backtracking
B) greedy algorithm
C) divide and conquer
D) dynamic programming
Explanation: In order to sort a given number, fast sort employs the divide and conquer technique. It divides the array into two sections around the pivot and then sorts both parts quickly.

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

Explanation: A random element is chosen as the pivot in a randomised fast sort. This is done to prevent the worst-case scenario of fast sort, where the input array is already sorted.

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

Explanation: When the input array is already sorted, the worst case time complexity is O(n2). Randomized simple sort helps to prevent this. The average case and best case time complexities, on the other hand, remain unchanged.




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

Explanation: Randomized fast sort’s auxiliary space complexity is O(log n), which is used to store the call stack generated by recursion. Since the value of log n is similar to 1, algorithms with a space complexity of O(log n) qualify as in place algorithms.

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

Explanation: Since randomised quick sort only helps in avoiding the worst case, the average case time complexity is the same as regular quick sort. It is the same as O. (n log n).

A Randomized Algorithm is an algorithm that uses random numbers to determine what to do next at any point in its logic. For example, in Randomized Fast Sort, we choose the next pivot based on a random number (or we randomly shuffle the array). The estimated time complexity of randomised quicksort is O(nLogn), but the worst case time complexity remains the same. In the worst-case scenario, the randomised function will always select the index of the corner variable. Insertion sort, Merge sort, Bubble sort, and other sorting algorithms are naturally stable. Some sorting algorithms, such as Heap Sort, Fast Sort, and others, are not.

Leave a Reply

Your email address will not be published. Required fields are marked *