Question

i) Pen down the algorithm for Radix sort.

ii) What is the complexity of Radix sort?

iii) Give any 2 real time examples of Radix sort.

Answer 1

Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers. Sorting is performed from least significant digit to the most significant digit.
Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest number among the list of numbers. For example, if the largest number is a 3 digit number then that list is sorted with 3 passes.

i)Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10 

ii)Since radix sort is a non-comparative algorithm, it has advantages over comparative sorting algorithms.Each key is looked at once for each digit (or letter if the keys are alphabetic) of the longest key. Hence, if the longest key has m digits and there are n keys, radix sort has order O(m.n).Here, we see that the size of the keys is not significant, and this algorithm is of linear complexity O(n).

iii)Radix sort is quite useful for very large in-memory sorts in a multiprocessor or cluster.Imagine that the entire dataset is in ram, distributed across a cluster. Each node sorts locally, based on the first digit of the key, The nodes then exchange data (what in MPI is called an ALL TO ALL collective) so that the data is distributed across the machine but with the first digit in overall order. Then the nodes move to the next key digit. Repeat until done.

Back in the era of punched cards, radix sorting was used for card sorting. To sort on a field, you'd begin at the last column and run the cards through the machine. They would land in different stacks according to their Hollerith code value in that column. You'd then remove the stacks in order and put them back into the hopper for the next pass. Repeat until all columns were sorted.

********************************************************************************************************************

In case of any doubt do ask in the comment section.Hope you like it