Radix sort is a peculiar algorithm for sorting integers or strings in lexicographic order.
How it works: {1/5} ↓
How it works: {1/5} ↓
Let's consider an array of integers.
The idea is to sort the numbers by looking at one digit at a time.
First, the numbers are sorted using the units column.
Then using the tens column, the hundreds column, and so on.
{2/5}
The idea is to sort the numbers by looking at one digit at a time.
First, the numbers are sorted using the units column.
Then using the tens column, the hundreds column, and so on.
{2/5}
The algorithm has 4 steps:
• find the maximum number and count its digits
• iterate through each digit, from the least to the most significant one
• sort the numbers based on the current digit
• return a sorted output array
{3/5}
• find the maximum number and count its digits
• iterate through each digit, from the least to the most significant one
• sort the numbers based on the current digit
• return a sorted output array
{3/5}
The 3rd step is usually performed using the counting sort algorithm because
- it's efficient, having an upper bound on the number of digits
- it's stable, preserving the existing order for numbers having the same current digit
{4/5}
- it's efficient, having an upper bound on the number of digits
- it's stable, preserving the existing order for numbers having the same current digit
{4/5}
The time complexity is O(d*n), where:
- n is the size of the array to sort
- d is the maximum number of digits
Indeed, counting sort is executed d times and it takes O(n).
The pace complexity is O(n) because counting sort requires a temporary array to sort.
{5/5}
- n is the size of the array to sort
- d is the maximum number of digits
Indeed, counting sort is executed d times and it takes O(n).
The pace complexity is O(n) because counting sort requires a temporary array to sort.
{5/5}
Thanks for reading!
If you liked it, I'd be grateful if you'd:
• like or retweet the first tweet
• follow @Franc0Fernand0 for more algorithms content
• subscribe my newsletter polymathicengineer .com (link in bio)
Your support encourages me to keep writing!
If you liked it, I'd be grateful if you'd:
• like or retweet the first tweet
• follow @Franc0Fernand0 for more algorithms content
• subscribe my newsletter polymathicengineer .com (link in bio)
Your support encourages me to keep writing!
Loading suggestions...