Sorting is a fundamental part of programming, helping organize data so it is easier to work with and analyze. One of the unique sorting algorithms is Radix Sort. Unlike simpler algorithms like Bubble Sort or Insertion Sort that compare elements directly, Radix Sort sorts numbers digit by digit, starting from the least significant digit to the most significant. This makes it especially efficient for large datasets of integers or numbers with many digits. By learning Radix Sort, beginners can understand a different approach to sorting that relies on positional value rather than direct comparisons.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is widely used in applications where performance matters, especially when sorting large lists of numbers like IDs, phone numbers, or large datasets in banking and computing systems. Learning Radix Sort in Ruby helps beginners explore arrays, loops, and the logic of grouping elements by digit. In this article, we will walk through multiple ways to implement Radix Sort, including traditional loops, recursive approaches, and sorting in both ascending and descending orders. This will give you a complete understanding of how the algorithm works and how to apply it effectively.
Program 1: Radix Sort Using Loops
This first program demonstrates Radix Sort using loops. It sorts a predefined array of integers in ascending order.
# Program 1: Radix Sort using loops
def counting_sort(array, exp)
n = array.length
output = Array.new(n, 0)
count = Array.new(10, 0)
array.each do |num|
index = (num / exp) % 10
count[index] += 1
end
(1...10).each do |i|
count[i] += count[i - 1]
end
(n - 1).downto(0) do |i|
index = (array[i] / exp) % 10
output[count[index] - 1] = array[i]
count[index] -= 1
end
(0...n).each { |i| array[i] = output[i] }
end
def radix_sort(array)
max_num = array.max
exp = 1
while max_num / exp > 0
counting_sort(array, exp)
exp *= 10
end
array
end
numbers = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_array = radix_sort(numbers)
puts "Sorted array: #{sorted_array}"In this program, we use counting sort as a subroutine to sort elements based on each digit. The algorithm starts with the least significant digit and moves to the most significant, ensuring numbers are sorted correctly. Beginners will find this approach useful because it demonstrates sorting in steps and shows how numbers are grouped and placed systematically.
Program 2: Radix Sort in Descending Order
Radix Sort can be adapted to sort numbers in descending order. This version reverses the placement of numbers in the counting sort stage.
# Program 2: Radix Sort in descending order
def counting_sort_desc(array, exp)
n = array.length
output = Array.new(n, 0)
count = Array.new(10, 0)
array.each do |num|
index = (num / exp) % 10
count[index] += 1
end
(8).downto(0) { |i| count[i] += count[i + 1] }
(n - 1).downto(0) do |i|
index = (array[i] / exp) % 10
output[count[index] - 1] = array[i]
count[index] -= 1
end
(0...n).each { |i| array[i] = output[i] }
end
def radix_sort_desc(array)
max_num = array.max
exp = 1
while max_num / exp > 0
counting_sort_desc(array, exp)
exp *= 10
end
array
end
numbers = [121, 432, 564, 23, 1, 45, 788]
sorted_array = radix_sort_desc(numbers)
puts "Sorted array (descending): #{sorted_array}"Here, the counting array is updated in reverse order to prioritize larger digits first. Beginners can see that small changes in the logic of placement can control the sorting order, making the algorithm flexible for different needs.
Program 3: Radix Sort Using Recursion
Radix Sort can also be implemented recursively, where each digit level is handled in a recursive call. This approach helps beginners understand recursion while applying Radix Sort.
# Program 3: Radix Sort using recursion
def counting_sort_recursive(array, exp)
n = array.length
output = Array.new(n, 0)
count = Array.new(10, 0)
array.each { |num| count[(num / exp) % 10] += 1 }
(1...10).each { |i| count[i] += count[i - 1] }
(n - 1).downto(0) do |i|
index = (array[i] / exp) % 10
output[count[index] - 1] = array[i]
count[index] -= 1
end
(0...n).each { |i| array[i] = output[i] }
end
def radix_sort_recursive(array, exp = 1)
max_num = array.max
return array if exp > max_num
counting_sort_recursive(array, exp)
radix_sort_recursive(array, exp * 10)
end
numbers = [329, 457, 657, 839, 436, 720, 355]
sorted_array = radix_sort_recursive(numbers)
puts "Sorted array (recursive): #{sorted_array}"In this recursive version, each call processes one digit level, from least significant to most significant. Beginners can appreciate how recursion replaces loops while maintaining the same logic. It also emphasizes the divide-and-process approach in sorting algorithms.
Program 4: Radix Sort for Strings Representing Numbers
Radix Sort can handle strings of digits by converting them to integers during processing. This program sorts a predefined array of numeric strings.
# Program 4: Radix Sort for strings
def counting_sort(array, exp)
n = array.length
output = Array.new(n, 0)
count = Array.new(10, 0)
array.each do |num|
index = (num / exp) % 10
count[index] += 1
end
(1...10).each do |i|
count[i] += count[i - 1]
end
(n - 1).downto(0) do |i|
index = (array[i] / exp) % 10
output[count[index] - 1] = array[i]
count[index] -= 1
end
(0...n).each { |i| array[i] = output[i] }
end
def radix_sort(array)
max_num = array.max
exp = 1
while max_num / exp > 0
counting_sort(array, exp)
exp *= 10
end
array
end
def radix_sort_strings(array)
int_array = array.map(&:to_i)
sorted_array = radix_sort(int_array)
sorted_array.map(&:to_s)
end
numbers = ["170", "45", "75", "90", "802", "24", "2", "66"]
sorted_strings = radix_sort_strings(numbers)
puts "Sorted strings: #{sorted_strings}"This example is useful for beginners working with text-based numeric data. By converting strings to integers and applying Radix Sort, we see that the algorithm is versatile and can handle multiple data types efficiently. It also reinforces the idea that sorting is about comparing values rather than the type of data.
Frequently Asked Questions (FAQ)
Radix Sort often raises questions for beginners. Here are some common queries:
Q1: What is the time complexity of Radix Sort?
Radix Sort has a time complexity of O(nk), where n is the number of elements and k is the number of digits. It is efficient for large arrays with small numbers of digits.
Q2: Is Radix Sort stable?
Yes, Radix Sort is stable because it preserves the relative order of equal elements during each counting sort stage.
Q3: Can Radix Sort sort negative numbers?
Radix Sort works naturally with non-negative integers. Sorting negative numbers requires additional handling, such as separating positive and negative numbers.
Q4: When should I use Radix Sort?
Radix Sort is ideal for sorting large sets of integers, IDs, phone numbers, or datasets where the number of digits is limited. It is less suitable for general-purpose sorting of floating-point numbers or strings with varying lengths.
Conclusion
In this article, we explored how to implement Radix Sort in Ruby using loops, descending order, recursion, and numeric strings. Radix Sort is a powerful algorithm that introduces beginners to digit-based sorting, stable sorting, and efficient array processing. By practicing these examples, you will gain a deeper understanding of sorting logic beyond simple comparisons. Radix Sort is especially useful for large numeric datasets, and experimenting with it in Ruby will help you build confidence in applying algorithmic thinking to real-world problems.
