Radix Sort Algorithm
The algorithm can be described as follows:
- Take the array. Check whether the number of digits in every array element is the same. If it is not the same, make it the same by using 0 before MSB.
- Find how many buckets are needed. Now, if you are given a decimal number, the digit will fall in the range of 0 to 9, so take 10 buckets. If you are given a string, then characters will fall in the range a-z (26 alphabets), so consider 0 – 25 buckets.
- Begin with the LSB (leftmost bit/character) and place the number based on the LSB in the appropriate bucket number. (Do not sort within the buckets). Just concatenate from the buckets and append the numbers in an empty array.
- Once it is done with one’s place (LSB), follow step 3 again for ten’s place, the hundred’s place, and so on until the MSB is reached.
- The last output will be the resultant sorted array.
Illustration:
Consider array arr[] = {22, 72, 62, 32, 82, 142}
We will sort based on LSB to MSB (keeping the number of digits the same in every number). The numbers will be:
022, 072, 062, 032, 082, 142We will have 10 buckets ranging from 0 to 9. Start from one place.
PASS 1
0
1
2 -> 022 -> 072 -> 062 -> 042 -> 032 -> 082 -> 142
3
4
5
6
7
8
9
Resulting list: {022, 072, 062, 042, 032, 082, 142}PASS 2
0
1
2 -> 022
3 -> 032
4 -> 042 -> 142
5
6 -> 062
7 -> 072
8 -> 082
9
Resulting list: {022, 032, 042, 142, 062, 072, 082}PASS 3
0 -> 022 -> 032 -> 042 -> 062 -> 072 -> 082
1 -> 142
2
3
4
5
6
7
8
9
Resulting list: {022, 032, 042, 062, 072, 082, 142}
Below are some major differences between Radix Sort and Bucket Sort:
Feature |
RADIX SORT |
BUCKET SORT |
---|---|---|
Base of approach | Buckets are based on the base of the number. If we are using decimal numbers, we will have 10 buckets. If we are using the same for alphabets, we will have 26 buckets. | The buckets are based on range, and the range is dependent on maximum and minimum numbers within the array. |
sorting | In radix sort, we don’t sort the elements after inserting them into the respective buckets. | In bucket sort, we sort the elements after inserting them into the bucket. |
Number of Passes | The number of passes one needs to perform for radix sort is the number of digits. If the 3-digit number, we need to perform 3 passes; if the 6-digit number, we need to perform 6 passes. | The number of passes one needs to perform for bucket sorting is 2. (One for inserting each element into a bucket and the other for sorting the elements within the bucket). |
Time Complexity | O (d*(n+b)) d = number of digits, n = number of array elements, b = base | In the worst-case scenario, O(n+k) [If we use a linked list to represent every element inside the bucket, then it will be O (n*n)]. |
uses | When the array elements are sparse (scattered), radix sort is used. | Bucket sort is used when the array elements are dense (nearby). |
It was found that bucket sort is faster as compared to radix sort, but it uses more memory when compared to radix sort.
Radix Sort vs Bucket Sort
We have two standard sorting algorithms, named bucket sort and radix sort. They both share differences and similarities. Let’s explore some similarities, differences, advantages, and disadvantages here in more detail.