What is Radix Sort? Its example with solution using bucket arrays.

Radix-sort is a generalization of BucketSort that uses multiple bucket arrays, the bin sorting approach can be generalised in a technique that is known as radix sorting.

Radix-sort  are two types of RadixSorts: MSD RadixSort and LSD RadixSort. LSD RadixSort works on the least significant digit first. As such, it right-aligns its values, so it is suitable for sorting integers. MSD RadixSort works on the most significant digit first, so it left-aligns its values. It is often used to quickly sort a list of strings. 

BucketSort doesn’t work because range is too big – would run in  Ω(n2)

Here is the Some example Radix sort using Bucket Array.

Example 1:

Problem:  Use RadixSort, with two bucket arrays and radix = 11, to sort the following array:

[63, 1, 48, 53, 24, 10, 12, 30, 100, 115, 17].

Show all steps of the sorting procedure. Then explain why the running time is O(n).

Solution:

Let us assume Remainder array r[] and Quotient array q[]. 

Calculate the remainder and put the respective bucket. let us take first index value 63, then 63 %11 will be 8, Now 63 put in 8th bucket of give array.and so on.

r[] =

	100 12 1	24		48	115	17		30 63	53	10
0	1	2	3	4	5	6	7	8	9	10

Now our array will become, put all the value from left to right.

[1,12,100,24,48,115,17,63,30,53,10]

Now We are going to find the out the new Quotient value for new bucket, because we are going to only use two bucket.

let us take first index of array 1. then 1/11 , it gives 0, now 1 put in 0th bucket, in below table and so on.

q[]=

10 1	17 12	30 24		53 48	63				100	115
0	1	2	3	4	5	6	7	8	9	10

Now our array will become, put all the value from left to right.

and final sorted array using two bucket is: Return: [1, 10, 12, 17, 24, 30, 48, 53, 63, 100, 115]

Running Time: O(n):

•   Initializing each of the bucket arrays costs O(n)
•  Populating r[] and q[] costs O(n)
• Reading output from q[] is O(n)

Example 2:

Problem: Use RadixSort, with two bucket arrays and radix = 6, to sort the following array:

[1, 8, 3, 2, 34, 21].

Show all steps of the sorting procedure. Then explain why the running time is O(n).

What would be the running time if you used ONE bucket?

Solution:

Let us assume Remainder array r[] and Quotient array q[]. 

Calculate the remainder and put the respective bucket. let us take first index value 1, then 1 %6 will be 1, Now 1 put in 1st bucket of give array.and so on.

r[] =

	1	2 8	21 3	34
0	1	2	3	4	5

Now our array will become, put all the value from left to right.

[1,8,2,3,21,34]

Now We are going to find the out the new Quotient value for new bucket, because we are going to only use two bucket.

let us take first index of array 1. then 1/6 , it gives 0, now 1 put in 0th bucket, in below table and so on.

q[]=

3 2 1	8		21		34
0	1	2	3	4	5

Now our array will become, put all the value from left to right.

and final sorted array using two bucket is: Return: [1, 2, 3, 8, 21, 34]

The formula used are

1. Bucket r - use input values x and remainder using mod 6.

2. Bucket q needs to be filled by reading values (left to right) from bucket r but divided by 6.

We know there should be Running Time: O(n):

1. Initializing each of the bucket arrays costs O(n)
2. Populating r[] and q[] costs O(n)
3. Reading output from q[] is O(n)

If one bucket is used, then we would need n^2 size as the range is close to 6^2 where 6 is the number of inputs. So, the time would be O(n^2).


See more  en.wikipedia.org/wiki/Radix_sort 

Happy Coding !!!