Sorting

Question 81

Which of the following algorithms sort n integers, having the range 0 to (n ² – 1), in ascending order in O(n) time ?

A	Selection sort
B	Bubble sort
C	Radix sort
D	Insertion sort

AlgorithmsSortingUGC NET CS 2015 Jun- paper-2

Question 81 Explanation:

Consider sorting n integers in the range 0 to n ² – 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.

Correct Answer: C

Question 81 Explanation:

Consider sorting n integers in the range 0 to n ² – 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.