 Download Algorithm & Program

Radix Sort is an example of External Sort.
The number of pass required to sort element in Radix sort depends on the number of digits in the Maximum number among list. If the list having a maximum number with 4 digits then we have to perform 4 pass.
In Radix Sort technique we use ten buckets for the digits 0 to 9.
During First PASS we scan each element from the list and separate its unit digit and according to its unit digit the number is placed in appropriate bucket. After the completion of first pass we arrange the numbers from bucket 0 to 9.
During second PASS we scan each element from the newly arranged list and separate next higher digit and according to that digit the number is placed in appropriate bucket. After the completion of second PASS we arrange the numbers from bucket 0 to 9.
Same process is repeated for all PASS. After completion of last PASS all the elements in the list are sorted.

Consider the following set of data:
42 23 74 11 65 57 94 36 99 87 70 81 61
In above example maximum number is 99 having 2 digits. So we need to perform two PASS.
Pass 1:
During first PASS we separate the unit digit of the number and place the number in to appropriate bucket according to its unit digit.
For example the first number is 42 so we separate the unit digit of the number 42 which is 2 so we place the number in bucket 2. Same procedure is repeated for remaining numbers.
After first PASS the numbers in each bucket are as follow:

 61 81 94 87 70 11 42 23 74 65 36 57 99 Pocket 0 1 2 3 4 5 6 7 8 9

Now arrange the numbers from bucket 0 to 9. The numbers after first pass are as follows:
70 11 81 61 42 23 74 94 65 36 57 87 99
Pass 2:
During second PASS we separate the next higher digit of the number and place the number in to appropriate bucket according to its digit.
After second PASS the numbers in each bucket are as follow:

 65 74 87 99 11 23 36 42 57 61 70 81 94 Pocket 0 1 2 3 4 5 6 7 8 9

Now arrange the number according to their bucket. The numbers after second pass are as follows:
11 23 36 42 57 61 65 70 74 81 87 94 99 Download Algorithm & Program