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

//Hope this algorithm helps you

// If u face any doubt feel free to ask me in the comments

//I will be very happy to solve them

Ans i) Algorithm for Radix sort:

There are a total of 8 steps in the algorithm shown below:

Let A be a linear array of n elements A[1], A[2], A[3]............A[n]. Digit is the total number of digit in the largest element in array A.

1. Input n number of elements in an array A.
2. Find the total number of digits in the largest element in the array.
3. Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
4. Initialize the bucket j=0 and repeat the steps 5until (j<n).
5. Compare the i^th position of each element of the array with bucket number and place it in the corresponding bucket.
6. Read the elements (S) of the bucket from 0^th bucket to 9^th bucket and from the first position to the higher one to generate new array A.
7. Display the sorted array A.
8. Exit.

Ans ii) Time complexity:

Time required for the radix sort method depends on the number of digits and the elements in the array. Suppose A is an array of n elements A[1], A[2]... A[n] and let r denote the radix( for example r=10 for decimal digits, r=26 for English letters). If A[1] is the largest number then A! Can be represented. Then radix sort require s passes. In passes, each element is compared with the bucket elements.

So the radix sort requires the total comparison f(n) of: F(n) < = r x s x n

Worst case

In the worst case s = n so F(n) = O(n2)

Best case

In the best case s = logn so f(n) = (nlogn)

Average case

It is very hard to define the time complexity. Because it will depend on the choice of the radix r and also the number of a digit on largest elements (i.e number of passes) but on an average (log n) comparison is required so f(n) = O(nlogn)

Ans 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.

IIRC this design was used at my old company for runs of the Terasort benchmark, which sorts a terabyte dataset, entirely in memory.