Data Structures & Algorithms Multiple Choice Questions on “MSD Radix Sort”.
1. How many comparisons will be made to sort the array arr = {1, 5, 3, 8, 2} using MSD radix sort?
a) 5
b) 7
c) 9
d) 0
Answer: d
Clarification: As MSD radix sort is an example of non comparison sort so it is able to sort an array without making any comparison. So the answer should be 0.
2. What is the full form of MSD in MSD radix sort?
a) most significant digit
b) many significant digit
c) more significant digit
d) must significant digit
Answer: a
Clarification: MSD stands for Most Significant Digit. It is named so because in this algorithm the processing begins from the most significant digit.
3. Which of the following combines qualities of MSD radix sort and LSD radix sort? Answer: d 4. Which of the following is the most suitable definition of radix sort? Answer: a 5. Which of the following is an alternate name of MSD radix sort? Answer: b 6. Which of the following is not true about MSD radix sort? Answer: c 7. MSD radix sort should be preferred over LSD radix sort when we have to maintain the original relative order. Answer: b 8. What is the average time complexity of MSD radix sort (w= bits required to store each key)? Answer: b 9. MSD radix sort is an in place sorting algorithm. Answer: b 10. Which of the following statement is not a stable sorting algorithm? Answer: b 11. Which of the following is not true about radix sort? Answer: b 12. What is the advantage of radix sort over quick sort? Answer: a 13. What will be the order of elements of the array arr = {23, 67, 143, 654, 43} after first iteration of MSD sort is complete? Answer: b
a) in-place MSD radix sort
b) stable MSD radix sot
c) 3 way radix quick sort
d) forward radix sort
Clarification: Forward radix sort combines the qualities of MSD and LSD radix sort. The sorting is done by separating the strings into groups.
a) It is a non comparison based integer sort
b) It is a comparison based integer sort
c) It is a non comparison based non integer sort
d) It is a comparison based non integer sort
Clarification: Radix sort is a non-comparison based integer sort. It sorts the given data by grouping keys which share the same significant position value.
a) bottom up radix sort
b) top down radix sort
c) forward radix sort
d) backward radix sort
Clarification: Top down radix sort is an alternate name of MSD radix sort. It is because in this algorithm the processing starts from the most significant digit and end at least significant digit.
a) its processing starts from the most significant digit
b) it is not a stable sort
c) it is an in place sorting algorithm
d) it is non comparison based sort
Clarification: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.
a) True
b) False
Clarification: MSD radix sort is not a stable sort whereas LSD radix sort is stable. So when we require to preserve the original order then in that case we should prefer LSD radix sort.
a) O(n + w)
b) O(n.w)
c) O(n2)
d) O(n log n)
Clarification: Time complexity of radix sort is O(n.w). It performs better than quick sort when we have log n bits for every digit.
a) True
b) False
View Answer
Clarification: MSD radix sort takes non constant time for sorting the input data. So it is not an in place sorting algorithm.
a) LSD radix sort
b) MSD radix sort
c) Counting sort
d) Pigeonhole sort
View Answer
Clarification: MSD radix sort is not a stable sort. It is because the elements with identical values do not appear in the same order in the output array as they were in the input array.
a) Radix sort performs better than quick sort when we have log n bits for every digit
b) Radix sort has better cache performance than quick sort
c) Radix sort has higher values of constant factor in asymptotic notation
d) Radix sort takes more space than quick sort
Clarification: Quick sort has a better cache performance than radix sort. Radix sort also takes more space as compared to quick sort.
a) radix sort performs better than quick sort when we have log n bits for every digit
b) radix sort has lesser space complexity
c) radix sort is not a comparison based sorting technique
d) radix sort has better cache performance than quick sort
Clarification: Radix sort performs better than quick sort when we have log n bits for every digit. But radix sort takes more space as compared to quick sort.
a) 23, 43, 67, 143, 654
b) 23, 67, 43, 143, 654
c) 23, 67, 143, 654, 43
d) 23, 143, 43, 654, 67
Clarification: In the first iteration the array is sorted according to the most significant digit I.e. hundreds place value. So the order of elements will be 23, 67, 43, 143, 654.