October 28, 2023
October 28, 2023
October 28, 2023
###### Sorting
October 28, 2023
 Question 81
Which of the following algorithms sort n integers, having the range 0 to (n​ 2​ – 1), in ascending order in O(n) time ?
 A Selection sort B Bubble sort C Radix sort D Insertion sort
Question 81 Explanation:
Consider sorting n integers in the range 0 to n​ 2​ – 1. We do it in two phases.
Phase 1:
1. We use n bins, one for each of the integers 0,1,.., n-1. We place each integer i on the list to be sorted into the bin numbered (i mod n) each bin will then contain a list of integers leaving the same remainder when divided by n.
At the end, we concatenate the bins in order to obtain a list L.
Phase 2:
1. The integers on the list L are redistributed into bins, but using the bin selection
function: ⌊i/n⌋
2. Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.
Question 81 Explanation:
Consider sorting n integers in the range 0 to n​ 2​ – 1. We do it in two phases.
Phase 1:
1. We use n bins, one for each of the integers 0,1,.., n-1. We place each integer i on the list to be sorted into the bin numbered (i mod n) each bin will then contain a list of integers leaving the same remainder when divided by n.
At the end, we concatenate the bins in order to obtain a list L.
Phase 2:
1. The integers on the list L are redistributed into bins, but using the bin selection
function: ⌊i/n⌋
2. Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.