Radix Sort is a special sorting algorithm that works very differently from common comparison-based sorts like Bubble Sort or Quick Sort. Instead of comparing numbers with each other, Radix Sort looks at individual digits of numbers and sorts them step by step. It usually starts from the least significant digit, such as the ones place, and moves toward the most significant digit. Because of this unique approach, Radix Sort can be very fast for certain types of data.
Radix Sort matters because it is widely used when working with large sets of integers, such as IDs, phone numbers, zip codes, or account numbers. In these cases, Radix Sort can be faster than many traditional sorting algorithms. In this article, you will learn how to implement Radix Sort in Lua using simple and clear programs. Each example is written in plain English style so beginners can easily understand how the algorithm works and how to use it in real programs.
Program 1: Basic Radix Sort using loops
This program shows a basic Radix Sort implementation in Lua using loops and a helper function. It works with positive integers and uses predefined data so you can run it immediately. This is the best place to start if you are new to Radix Sort.
-- Basic Radix Sort in Lua
function getMax(arr)
local max = arr[1]
for i = 2, #arr do
if arr[i] > max then
max = arr[i]
end
end
return max
end
function countingSort(arr, exp)
local output = {}
local count = {}
for i = 0, 9 do
count[i] = 0
end
for i = 1, #arr do
local index = math.floor(arr[i] / exp) % 10
count[index] = count[index] + 1
end
for i = 1, 9 do
count[i] = count[i] + count[i - 1]
end
for i = #arr, 1, -1 do
local index = math.floor(arr[i] / exp) % 10
output[count[index]] = arr[i]
count[index] = count[index] - 1
end
for i = 1, #arr do
arr[i] = output[i]
end
end
function radixSort(arr)
local max = getMax(arr)
local exp = 1
while math.floor(max / exp) > 0 do
countingSort(arr, exp)
exp = exp * 10
end
end
local numbers = {170, 45, 75, 90, 802, 24, 2, 66}
radixSort(numbers)
for i = 1, #numbers do
io.write(numbers[i] .. " ")
endThis program works by sorting numbers digit by digit, starting from the ones place and moving left. Counting Sort is used internally because it is stable and works well with digits. Beginners can think of this as sorting numbers multiple times, each time focusing on one digit.
Program 2: Radix Sort with clearer variable names
This version improves readability by using clearer variable names and slightly reorganized logic. It is helpful for beginners who want code that reads more like plain English.
-- Radix Sort with readable variable names
function findMaximum(values)
local maximum = values[1]
for i = 2, #values do
if values[i] > maximum then
maximum = values[i]
end
end
return maximum
end
function sortByDigit(values, digitPlace)
local sorted = {}
local digitCount = {}
for i = 0, 9 do
digitCount[i] = 0
end
for i = 1, #values do
local digit = math.floor(values[i] / digitPlace) % 10
digitCount[digit] = digitCount[digit] + 1
end
for i = 1, 9 do
digitCount[i] = digitCount[i] + digitCount[i - 1]
end
for i = #values, 1, -1 do
local digit = math.floor(values[i] / digitPlace) % 10
sorted[digitCount[digit]] = values[i]
digitCount[digit] = digitCount[digit] - 1
end
for i = 1, #values do
values[i] = sorted[i]
end
end
function radixSort(values)
local maximum = findMaximum(values)
local digitPlace = 1
while math.floor(maximum / digitPlace) > 0 do
sortByDigit(values, digitPlace)
digitPlace = digitPlace * 10
end
end
local data = {329, 457, 657, 839, 436, 720, 355}
radixSort(data)
for _, value in ipairs(data) do
io.write(value .. " ")
endThis program behaves the same as the first one, but the naming makes it easier to follow. Beginners can quickly see what each function is responsible for. Clear naming is a good habit that makes your programs easier to maintain and debug.
Program 3: Radix Sort with step-by-step output
This program prints the array after each digit pass so learners can see how Radix Sort progresses. It is very useful for understanding how the algorithm works internally.
-- Radix Sort with step-by-step output
function getMax(arr)
local max = arr[1]
for i = 2, #arr do
if arr[i] > max then
max = arr[i]
end
end
return max
end
function countingSort(arr, exp)
local output = {}
local count = {}
for i = 0, 9 do
count[i] = 0
end
for i = 1, #arr do
local index = math.floor(arr[i] / exp) % 10
count[index] = count[index] + 1
end
for i = 1, 9 do
count[i] = count[i] + count[i - 1]
end
for i = #arr, 1, -1 do
local index = math.floor(arr[i] / exp) % 10
output[count[index]] = arr[i]
count[index] = count[index] - 1
end
for i = 1, #arr do
arr[i] = output[i]
end
for _, v in ipairs(arr) do
io.write(v .. " ")
end
print()
end
function radixSort(arr)
local max = getMax(arr)
local exp = 1
while math.floor(max / exp) > 0 do
print("After sorting with digit place " .. exp .. ":")
countingSort(arr, exp)
exp = exp * 10
end
end
local sample = {121, 432, 564, 23, 1, 45, 788}
radixSort(sample)By printing the array after each digit sorting step, beginners can clearly see how numbers slowly move into the correct order. This removes much of the mystery around Radix Sort. It is especially helpful when learning or teaching the algorithm.
Program 4: Radix Sort wrapped in a reusable function
This version focuses on making Radix Sort reusable in other Lua programs. It keeps the logic clean and easy to call with different datasets.
-- Reusable Radix Sort function
function radixSort(arr)
local function getMaxValue()
local max = arr[1]
for i = 2, #arr do
if arr[i] > max then
max = arr[i]
end
end
return max
end
local function countingSort(exp)
local output = {}
local count = {}
for i = 0, 9 do
count[i] = 0
end
for i = 1, #arr do
local digit = math.floor(arr[i] / exp) % 10
count[digit] = count[digit] + 1
end
for i = 1, 9 do
count[i] = count[i] + count[i - 1]
end
for i = #arr, 1, -1 do
local digit = math.floor(arr[i] / exp) % 10
output[count[digit]] = arr[i]
count[digit] = count[digit] - 1
end
for i = 1, #arr do
arr[i] = output[i]
end
end
local max = getMaxValue()
local exp = 1
while math.floor(max / exp) > 0 do
countingSort(exp)
exp = exp * 10
end
end
local values = {88, 410, 1772, 20, 5, 999}
radixSort(values)
for _, v in ipairs(values) do
io.write(v .. " ")
endThis approach is useful when you want a clean and reusable sorting function. Beginners can copy this function into other projects without changing much. It shows how Radix Sort can fit naturally into real Lua programs.
Program 5: Radix Sort handling negative numbers
By default, Radix Sort works only with non-negative integers. This final program tweaks the logic so it can handle negative numbers by separating them and combining the results.
-- Radix Sort handling negative numbers
function radixSortPositive(arr)
local function getMax(arr)
local max = arr[1]
for i = 2, #arr do
if arr[i] > max then
max = arr[i]
end
end
return max
end
local function countingSort(arr, exp)
local output = {}
local count = {}
for i = 0, 9 do
count[i] = 0
end
for i = 1, #arr do
local index = math.floor(arr[i] / exp) % 10
count[index] = count[index] + 1
end
for i = 1, 9 do
count[i] = count[i] + count[i - 1]
end
for i = #arr, 1, -1 do
local index = math.floor(arr[i] / exp) % 10
output[count[index]] = arr[i]
count[index] = count[index] - 1
end
for i = 1, #arr do
arr[i] = output[i]
end
end
local max = getMax(arr)
local exp = 1
while math.floor(max / exp) > 0 do
countingSort(arr, exp)
exp = exp * 10
end
end
function radixSortWithNegatives(arr)
local positives = {}
local negatives = {}
for _, v in ipairs(arr) do
if v >= 0 then
table.insert(positives, v)
else
table.insert(negatives, -v)
end
end
if #positives > 0 then
radixSortPositive(positives)
end
if #negatives > 0 then
radixSortPositive(negatives)
end
local index = 1
for i = #negatives, 1, -1 do
arr[index] = -negatives[i]
index = index + 1
end
for i = 1, #positives do
arr[index] = positives[i]
index = index + 1
end
end
local mixedNumbers = {170, -45, 75, -90, 802, 24, -2, 66}
radixSortWithNegatives(mixedNumbers)
for _, v in ipairs(mixedNumbers) do
io.write(v .. " ")
endThis program works by separating negative and positive numbers, sorting them individually, and then merging them back together. Beginners can see how a limitation of Radix Sort can be handled with a smart workaround. This makes the algorithm more practical for real-world data.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Radix Sort in Lua and helps clear confusion.
Q1. Is Radix Sort faster than Quick Sort?
Radix Sort can be faster than Quick Sort for large lists of integers with limited digit length. However, Quick Sort is more flexible and works better for general data.
Q2. Does Radix Sort compare numbers directly?
No, Radix Sort does not compare numbers directly. It sorts numbers based on their digits using a stable sorting method.
Q3. Can Radix Sort handle floating-point numbers?
Standard Radix Sort does not handle floating-point numbers directly. Extra steps are needed to convert or scale them before sorting.
Q4. Is Radix Sort stable?
Yes, Radix Sort is stable as long as the internal sorting method, like Counting Sort, is stable.
Q5. When should I use Radix Sort in Lua?
Radix Sort is best when sorting large lists of non-negative integers, such as IDs or codes, where performance matters.
Conclusion
Radix Sort is a powerful and interesting sorting algorithm that works in a unique way by focusing on digits instead of comparisons. In this article, you explored multiple Lua programs that implement Radix Sort, starting from a simple version and moving toward more practical examples, including handling negative numbers. Each program showed a different way to understand and apply the algorithm.
By practicing these Lua programs and experimenting with different numbers, you can build strong confidence in both sorting algorithms and Lua programming. Keep exploring, keep coding, and do not be afraid to dig deeper into how algorithms work behind the scenes. With steady practice, Radix Sort and many other algorithms will become easy and familiar.
