Data Structures & Algorithms Multiple Choice Questions on “Quicksort”.
1. Quick sort is a __________
a) greedy algorithm
b) divide and conquer algorithm
c) dynamic programming algorithm
d) backtracking algorithm
Answer: b
Clarification: Quick sort is a divide and conquer algorithm. Quick sort first partitions a large array into two smaller sub-arrays. And then recursively sorts the sub-arrays.
2. What is the worst case time complexity of the Quick sort?
a) O(nlogn)
b) O(n)
c) O(n3)
d) O(n2)
Answer: d
Clarification: The worst case running time for Quick sort is O(n2). In Quick sort, the worst case behaviour occurs when the partitioning routine produces two sub-arrays one with n – 1 element and other with 0 elements.
3. 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
View Answer
Answer: b
Clarification: 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
4. 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
View Answer
Answer: a
Clarification: The best case analysis of quick sort occurs when the partition splits the array into two subarrays, each of size no more than n/2 since one is of size n/2 and one of size (n/2) – 1.
5. Quick sort is a stable sorting algorithm.
a) True
b) False
Answer: b
Clarification: In stable sorting algorithm the records with equal keys appear in the same order in the sorted sequence as they appear in the input unsorted sequence. Quick sort does not preserve the relative order of equal sort items. Therefore, Quick sort is not a stable sort.
6. 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
Answer: b
Clarification: If there are n/4 elements in one sub-array then T(n/4) comparisons are needed for this sub-array. And T(3n/4) comparison are required for the rest 4n/5 elements, and cn is time required for finding the pivot. If there are more than n/4 elements in one sub-array then other sub-array will have less than 3n/4 elements and time complexity will be less than T(n/4) + T(3n/4) + cn.
7. 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
Answer: a
Clarification: If the input sequence is already sorted then worst case behaviour occurs for the Quick sort algorithm which use the first element as pivot. Therefore, the input sequence given in 22 25 56 67 89 will require a maximum number of comparisons.
8. 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
Answer: c
Clarification: 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.
9. 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
Answer: d
Clarification: The Quick sort is best suited to sort the array of 1 million elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst case behaviour and is almost always O(nlogn). And Quick sort requires little additional space and exhibits good cache locality.
10. Quick sort is a space-optimised version of ____
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Binary tree sort
Answer: d
Clarification: Quick sort is a space-optimised version of the binary tree sort. In binary sort tree, the elements are inserted sequentially into the binary search tree and Quick sort organises elements into a tree that is implied by the recursive calls.