Hello Friends, in this blog post I am going to let you know about the Radix Sort in Data Structure. Radix sort is a method that many people intuitively use when alphabetizing a large list of names.
Here the Radix is 26, the 26 letters of the alphabet specifically, the list of names are first sorted according to the first letter of each name.
That is, the names are arranged in 26 classes, where the first-class consist of those names that begin with ‘A’, the second class consists of those names that begin with ‘B’ and so on.
During the second pass, each class is alphabetized according to the second letter of the name, and so on. If no name contains, for example, more than 12 letters, the names are alphabetized with at most 12 passes.
The radix sort is the method used by a card sorter. A card sorter contains 13 receiving pockets labeled as follows-
9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 12, R (reject)
Each pocket other than R corresponds to a row on a card in which a hole can be punched. Decimal numbers, where the radix is 10, are punched in an obvious way and hence use only the first 10 pockets of the sorter.
The sorter uses a radix reverse-digit sort on numbers. It means that suppose a card sorter is given a collection of cards where each card contains a 3-digit number punched in columns 1 to 3.
The cards are first sorted according to the unit’s digit. On the second pass, the cards are sorted according to the tens digit. On the third and last pass, the cards are sorted according to the hundreds digit.
The following example illustrates this – suppose 9 cards are punched as follows-
348, 143, 361, 423, 538, 128, 321, 543, 366
Given to a card sorter, the numbers are sorted in three phases, as shown in fig 1, fig 2, and fig 3 respectively.
In the first pass of radix sort, the units digits are sorted into pockets. the pockets are pictured upside down, so 348 is at bottom of pocket 8.
The cards are collected pocket by pocket, from pocket 9 to pocket 0. Note that 361 will now be at bottom of the pile and 128 at the top of the pile. the cards are now reinput to the sorter.
If you still could not understand the first pass format and value insertion then here I will explain to you in a very simple language.
first, here we have to sort the three-digit number so we will have a total three passes to sort out the list. Further, we make a table of 10×10, mean 10 rows and 10 columns because we are sorting the decimal number.
Now as we know that in first pass we see the unit digit number to place the number in the table. our first number is 348, In this number 8 is our unit digit number now we insert this number in the 8th column corresponding to 348 row. as you can see this number insertion in fig 1.
In the second pass of radix sort, the tens digits are sorted into pockets. Again the cards are collected pocket by pocket and reinput to the sorter.
In the third and final pass of radix sort, the hundreds of digits are sorted into pockets. When the cards are collected after the third pass, the numbers are in the following order.
128, 143, 321, 348, 361, 366, 423, 538, 543
Thus the cards are now sorted.
In the case of any queries, you can write to us at firstname.lastname@example.org we will get back to you ASAP.
Hope! you would have enjoyed this post about ‘Radix Sort’.
Please feel free to give your important feedbacks in the comment section below.
Have a great time! Sayonara!