Sorting is a core concept in programming, and knowing how to sort data efficiently is crucial for building effective software. Radix Sort is a powerful sorting algorithm, particularly useful when dealing with large lists of numbers. Unlike comparison-based sorting algorithms like Quick Sort or Merge Sort, Radix Sort sorts numbers digit by digit, which allows it to achieve excellent performance in certain scenarios. It is commonly used in applications like data processing, digital systems, and anywhere large sequences of integers need to be sorted efficiently.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, learning Radix Sort is a great way to understand non-comparative sorting methods. The algorithm works by grouping numbers based on their individual digits, starting from the least significant digit (LSD) and moving to the most significant digit (MSD). This step-by-step approach ensures that the numbers are fully sorted without directly comparing them, which can feel a bit different from other sorting algorithms. By implementing Radix Sort in Dart, you get a hands-on understanding of both array manipulation and the logic behind digit-based sorting.
Program 1: Basic Radix Sort Using Least Significant Digit
This program demonstrates the standard Radix Sort approach using the least significant digit first. It sorts an array of integers by repeatedly grouping digits and combining them.
void radixSort(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
int exp = 1;
while (max ~/ exp > 0) {
countingSortByDigit(arr, exp);
exp *= 10;
}
}
void countingSortByDigit(List<int> arr, int exp) {
List<int> output = List.filled(arr.length, 0);
List<int> count = List.filled(10, 0);
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] ~/ exp) % 10;
count[index]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
int index = (arr[i] ~/ exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
void main() {
List<int> numbers = [170, 45, 75, 90, 802, 24, 2, 66];
print("Original List: $numbers");
radixSort(numbers);
print("Sorted List: $numbers");
}This program works by sorting each digit starting from the least significant one. The countingSortByDigit function groups numbers according to their current digit, ensuring stability in sorting. Beginners can understand how breaking down numbers into digits allows Radix Sort to operate efficiently without direct comparisons.
Program 2: Radix Sort Using Most Significant Digit
Radix Sort can also be implemented starting from the most significant digit (MSD). This approach sorts numbers recursively from the highest place value down to the lowest.
void radixSortMSD(List<int> arr, int exp) {
if (arr.length <= 1 || exp == 0) return;
List<List<int>> buckets = List.generate(10, (_) => []);
for (var number in arr) {
int index = (number ~/ exp) % 10;
buckets[index].add(number);
}
int i = 0;
for (var bucket in buckets) {
radixSortMSD(bucket, exp ~/ 10);
for (var number in bucket) {
arr[i++] = number;
}
}
}
void main() {
List<int> numbers = [170, 45, 75, 90, 802, 24, 2, 66];
int max = numbers.reduce((a, b) => a > b ? a : b);
int exp = 1;
while (max ~/ exp >= 10) exp *= 10;
print("Original List: $numbers");
radixSortMSD(numbers, exp);
print("Sorted List: $numbers");
}The MSD approach uses recursion to sort numbers by the most significant digit first. Beginners can see how breaking down the problem recursively makes the sorting process intuitive and organized, though it requires careful handling of sublists.
Program 3: Radix Sort for Negative Numbers
Standard Radix Sort handles only positive integers. This program demonstrates how to extend it to handle negative numbers as well.
void radixSort(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
int exp = 1;
while (max ~/ exp > 0) {
countingSortByDigit(arr, exp);
exp *= 10;
}
}
void countingSortByDigit(List<int> arr, int exp) {
List<int> output = List.filled(arr.length, 0);
List<int> count = List.filled(10, 0);
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] ~/ exp) % 10;
count[index]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
int index = (arr[i] ~/ exp) % 10;
output[count[index] - 1] = arr[i];
count[index]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
void radixSortWithNegatives(List<int> arr) {
List<int> positives = arr.where((x) => x >= 0).toList();
List<int> negatives = arr.where((x) => x < 0).map((x) => -x).toList();
radixSort(positives);
radixSort(negatives);
negatives = negatives.reversed.map((x) => -x).toList();
arr
..clear()
..addAll(negatives)
..addAll(positives);
}
void main() {
List<int> numbers = [170, -45, 75, -90, 802, 24, -2, 66];
print("Original List: $numbers");
radixSortWithNegatives(numbers);
print("Sorted List: $numbers");
}This program separates negative and positive numbers, sorts them individually using standard Radix Sort, and combines them afterward. Beginners can learn how simple transformations allow Radix Sort to handle broader cases.
Program 4: Radix Sort Using Buckets
Instead of counting sort, Radix Sort can use dynamic buckets for each digit. This approach simplifies handling digits and demonstrates a more visual way of sorting.
void radixSortBuckets(List<int> arr) {
int max = arr.reduce((a, b) => a > b ? a : b);
int exp = 1;
while (max ~/ exp > 0) {
List<List<int>> buckets = List.generate(10, (_) => []);
for (var number in arr) {
int index = (number ~/ exp) % 10;
buckets[index].add(number);
}
arr = buckets.expand((x) => x).toList();
exp *= 10;
}
print("Sorted List with Buckets: $arr");
}
void main() {
List<int> numbers = [170, 45, 75, 90, 802, 24, 2, 66];
print("Original List: $numbers");
radixSortBuckets(numbers);
}By using buckets, numbers are grouped according to their digits, making the process easier to visualize. Beginners can understand how bucket-based grouping is an intuitive way to sort numbers by each digit.
Program 5: Radix Sort with Strings Representing Numbers
Radix Sort can also sort string representations of numbers efficiently, which is useful in some data processing scenarios.
void radixSortStrings(List<String> arr) {
// Find the maximum length of strings
int maxLength = arr.map((x) => x.length).reduce((a, b) => a > b ? a : b);
// Pad numbers with leading zeros
List<String> paddedArr = arr.map((x) => x.padLeft(maxLength, '0')).toList();
// Radix sort from least significant digit to most significant
for (int i = maxLength - 1; i >= 0; i--) {
List<List<String>> buckets = List.generate(10, (_) => []);
for (var number in paddedArr) {
int digit = int.parse(number[i]);
buckets[digit].add(number);
}
paddedArr = buckets.expand((x) => x).toList();
}
// Remove the padding to get original numbers
List<String> sortedArr = paddedArr.map((x) => x.replaceFirst(RegExp(r'^0+'), '')).toList();
print("Sorted Strings: $sortedArr");
}
void main() {
List<String> numbers = ['170', '45', '75', '90', '802', '24', '2', '66'];
print("Original List: $numbers");
radixSortStrings(numbers);
}Sorting strings by their digits demonstrates Radix Sort’s flexibility. Beginners can learn how to adapt numerical algorithms to work with strings or other comparable sequences.
Frequently Asked Questions (FAQ)
Radix Sort is powerful but raises questions for beginners. Here are some common answers.
Q1: What is the time complexity of Radix Sort?
Radix Sort has O(nk) time complexity, where n is the number of elements and k is the number of digits in the largest number.
Q2: Can Radix Sort handle negative numbers?
Yes, by separating negatives and positives, then sorting and recombining, Radix Sort can handle negative numbers.
Q3: Is Radix Sort stable?
Yes, Radix Sort is stable, meaning equal elements maintain their relative order.
Q4: When should I use Radix Sort?
Radix Sort is ideal for large datasets of integers or fixed-length strings where comparisons are expensive.
Q5: Does Radix Sort work with strings?
Yes, Radix Sort can be adapted to sort strings that represent numbers or even fixed-length textual sequences.
Conclusion
Radix Sort is a versatile, efficient sorting algorithm, particularly suited for numbers or strings with digits. In this article, we explored multiple implementations, including LSD and MSD approaches, handling negative numbers, using buckets, and sorting strings.
For beginners, practicing Radix Sort helps develop skills in array manipulation, recursion, and problem-solving. Experimenting with different data types and techniques ensures a deeper understanding of how non-comparative sorting algorithms work, providing a strong foundation for efficient data processing in Dart.
