# Quicksort – Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Quicksort

1. Which is the safest method to choose a pivot element?
A) choosing a random element as pivot
B) choosing the first element as pivot
C) choosing the last element as pivot
D) median-of-three partitioning method

Explanation: This is the best method for selecting the pivot element since a random pivot is unlikely to reliably produce a bad partition.

2. What is the average running time of a quick sort algorithm?
A) O(N2)
B) O(N)
C) O(N log N)
D) O(log N)

Explanation: A quick sort algorithm’s best and average case analyses are found to be O mathematically (N log N).

3. Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
A) Merge sort
B) Shell sort
C) Insertion sort
D) Bubble sort

Explanation: The sub arrays are sorted using insertion sort and fast sort.
It is only seen at the very end.

4. Quick sort uses join operation rather than merge operation.
A) true
B) false

Explanation: Since join is a faster operation than merge, quick sort uses it.

5. How many sub arrays does the quick sort algorithm divide the entire array into?
A) one
B) two
C) three
D) four

Explanation: The entire array is split into two subarrays, the first of which contains elements less than the pivot element and the second of which contains elements greater than the pivot element.

6. Which is the worst method of choosing a pivot element?
A) first element as pivot
B) last element as pivot
C) median-of-three partitioning
D) random element as pivot

Explanation: Choosing the first element as the pivot is the worst approach since the pivot offers a weak partition if the input is pre-sorted or in reverse order.

7. Which among the following is the best cut-off range to perform insertion sort within a quick sort?
A) N=0-5
B) N=5-20
C) N=20-30
D) N>30

Explanation: To prevent nasty degenerate situations, a decent cut-off range is somewhere between N=5 and N=20.

8. Which of the following sorting algorithms is the fastest?
A) Merge sort
B) Quick sort
C) Insertion sort
D) Shell sort

Explanation: Because of its highly optimised inner loop, Quick Sort is the fastest known sorting algorithm.

9. Quick sort follows Divide-and-Conquer strategy.
A) True
B) False

Explanation: The array is divided into sub-arrays and then sorted in fast sort (divide-and-conquer strategy).

10. What is the worst case time complexity of a quick sort algorithm?
A) O(N)
B) O(N log N)
C) O(N2)
D) O(log N)

Explanation: A quick sort algorithm’s worst-case output has been calculated to be O. (N2).

11. Which of the following methods is the most effective for picking the pivot element?
A) first element
B) last element
C) median-of-three partitioning
D) random element

Explanation: The best method for selecting an acceptable pivot element is median-of-three partitioning. Choosing a pivot from the first, last, or random elements is ineffective.

12. Find the pivot element from the given input using median-of-three partitioning method.
8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
A) 8
B) 7
C) 9
D) 6

Explanation: Left element=8, right element=0,
Centre=[position(left+right)/2]=6.

13. Consider the Quick sort algorithm in which the partitioning procedure splits elements into two sub-arrays and each sub-array contains at least one-fourth of the elements. Let T(n) be the number of comparisons required to sort array of n elements. Then T(n)<=?
A) T(n) <= 2 T(n/4) + cn
B) T(n) <= T(n/4) + T(3n/4) + cn
C) T(n) <= 2 T(3n/4) + cn
D) T(n) <= T(n/3) + T(3n/4) + cn

Explanation: If one sub-array has n/4 elements, T(n/4) comparisons are needed for this sub-array. For the remaining 4n/5 elements, T(3n/4) comparison is needed, and cn is the time required to find the pivot. When one sub-array has more than n/4 elements, the other sub-array has less than 3n/4 elements, and the time complexity is less than T(n/4) + T(3n/4) + cn.

14. Consider the Quick sort algorithm which sorts elements in ascending order using the first element as pivot. Then which of the following input sequence will require a maximum number of comparisons when this algorithm is applied on it?
A) 22 25 56 67 89
B) 52 25 76 67 89
C) 22 25 76 67 50
D) 52 25 89 67 76

Explanation: If the input sequence has already been sorted, the Fast sort algorithm, which uses the first element as a pivot, will behave in the worst case. As a result, the input series 22 25 56 67 89 would necessitate the most number of comparisons.

15. A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. The minimum time needed to sort 200 elements will be approximately __________
A) 60.2 sec
B) 45.54 sec
C) 31.11 sec
D) 20 sec

Explanation: The Quick sort requires nlog2n comparisons in best case, where n is size of input array. So, 1000 * log21000 ≈ 9000 comparisons are required to sort 1000 elements, which takes 200 sec. To sort 200 elements minimum of 200 * log2200 ≈ 1400 comparisons are required. This will take 200 * 1400 / 9000 ≈ 31.11 sec.

16. Which one of the following sorting algorithm is best suited to sort an array of 1 million elements?
A) Bubble sort
B) Insertion sort
C) Merge sort
D) Quick sort

Explanation: The Fast sort is the best option for sorting a 1 million-element array. Fast sort is implemented in practise using a randomised version. In reality, randomised Fast sort algorithms almost never exhibit worst-case behaviour and are almost always O. (nlogn). Fast kind, on the other hand, takes up little extra space and has strong cache locality.

17. Quick sort is a space-optimised version of ____
A) Bubble sort
B) Selection sort
C) Insertion sort
D) Binary tree sort

Explanation: The binary tree sort is a space-optimized variant of fast sort. The elements are inserted sequentially into the binary search tree in binary sort tree, and Fast sort organises the elements into a tree indicated by the recursive calls.

18. Quick sort is a __________
A) greedy algorithm
B) divide and conquer algorithm
C) dynamic programming algorithm
D) backtracking algorithm

Explanation: A divide-and-conquer algorithm is used in fast sort. Fast sort divides a large array into two smaller sub-arrays before sorting it. The sub-arrays are then sorted recursively.

19. What is the worst case time complexity of the Quick sort?
A) O(nlogn)
B) O(n)
C) O(n3)
D) O(n2)

Explanation: Fast sort’s worst-case running time is O. (n2). When the partitioning routine generates two sub-arrays, one with n – 1 elements and the other with 0 elements, the worst case behaviour occurs in Fast sort.

20. Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after first phase, pivot is first element?
A) 6 4 3 7 11 9 14 12
B) 6 3 4 7 9 14 11 12
C) 7 6 14 11 9 4 3 12
D) 7 6 4 3 9 14 11 12

Explanation: Let’s apply Quick sort on the given sequence,
For first phase, pivot = 7
7     11     14     6     9     4     3     12
i                                              j
7     11     14    6     9    4     3     12
i                                    j
7     3     14     6     9     4     11     12
i                     j
7     3     4    6     9     14    11     12
i      j
7     3     4     6    9    14     11     12
j      i
6     3     4     7     9     14     11     12

21. The best case behaviour occurs for quick sort is, if partition splits the array of size n into __________
A) n/2 : (n/2) – 1
B) n/2 : n/3
C) n/4 : 3n/2
D) n/4 : 3n/4

Explanation: When the partition divides the array into two subarrays, each of size no more than n/2, the best case study of fast sort occurs since one is of size n/2 and the other is of size (n/2) – 1.

22. Quick sort is a stable sorting algorithm.
A) True
B) False

Explanation: Records with identical keys appear in the sorted sequence in the same order as they appear in the input unsorted sequence in a stable sorting algorithm. The relative order of equivalent sort objects is not preserved by fast sort. As a result, Fast sort isn’t a reliable sort.

23. Which of the following code performs the partition operation in QuickSort?
A)

```private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left > right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}```

B)

```private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left <= right)
{
while(arr[left] <= pivot_item)
{
left++;
}
while(arr[right] > pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}```

C)

```private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left <= right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}```

D)

```private static int partition(int[] arr, int low, int high)
{
int left, right, pivot_item = arr[low];
left = low;
right = high;
while(left > right)
{
while(arr[left] > pivot_item)
{
left++;
}
while(arr[right] <= pivot_item)
{
right--;
}
if(left < right)
{
swap(arr, left, right);
}
}
arr[low] = arr[right];
arr[right] = pivot_item;
return right;
}```

Explanation: The list is divided such that the elements to the left of the pivot are smaller than the pivot, while the elements to the right of the pivot are larger.

24. What is the best case complexity of QuickSort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Using the Divide and Conquer master theorem, the collection is partitioned into equal halves, and the complexity is found to be O. (nlogn).

25. The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
A) 1 and 3
B) 3 and 1
C) 2 and 6
D) 6 and 2

Explanation: The pivot elements are returned by the call to partition.

26. What is the average case complexity of QuickSort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Since the location of partition(split) is unknown, all(n) options are considered, and the average is calculated by adding all and dividing by n.

27. The given array is arr = {2,6,1}. What are the pivots that are returned as a result of subsequent partitioning?
A) 1 and 6
B) 6 and 1
C) 2 and 6
D) 1

Explanation: The list will be sorted using only one pivot, which is number one.

28. Which of the following is not true about QuickSort?
A) in-place algorithm
B) pivot position can be changed
D) can be implemented as a stable sort

Explanation: If a pivot is selected, its location in the sorted array is fixed and cannot be changed.

29. QuickSort can be categorized into which of the following?
A) Brute Force technique
B) Divide and conquer
C) Greedy algorithm
D) Dynamic programming

Explanation: The array is divided (partitioned) based on the pivot element, and then sorted accordingly.

30. Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array, partition returns the pivot element, we will see the code for partition very soon)
A)

```public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}```

B)

```public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high<low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}```

C)

```public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot);
quickSort(arr, pivot, high);
}
}```

D)

```public static void quickSort(int[] arr, int low, int high)
{
int pivot;
if(high>low)
{
pivot = partition(arr, low, high);
quickSort(arr, low, pivot);
quickSort(arr, pivot+2, high);
}
}```

Explanation: Recursive calls to quickSort sort the provided array based on the pivot returned by the call to partition.

31. What is the worst case complexity of QuickSort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: When the input list has been sorted already.

32. What is a randomized QuickSort?
A) The leftmost element is chosen as the pivot
B) The rightmost element is chosen as the pivot
C) Any element in the array is chosen as the pivot
D) A random number is generated which is used as the pivot

Explanation: QuickSort is randomised by either randomly arranging the input data in the array or selecting a random element in the array as a pivot.

Quicksort is a sorting algorithm that works in real time. It was created in 1959 by British computer scientist Tony Hoare and published in 1961, and it is still a widely used sorting algorithm. It can be slightly faster than merge sort and two to three times faster than heapsort when properly implemented. [incongruent] Quicksort is based on the divide-and-conquer strategy. It works by picking a ‘pivot’ element from the array and partitioning the remaining elements into two sub-arrays based on whether they are greater or less than the pivot. As a result, it’s also known as partition-exchange type. The sub-arrays are then recursively sorted. This can be done in-place and would only cost a small amount of money.