Bucket Sort is a simple and intuitive sorting algorithm that works especially well when numbers are evenly distributed over a known range. Instead of comparing elements again and again like many traditional sorting algorithms, Bucket Sort divides values into smaller groups called buckets. Each bucket holds a range of values, and once the values are placed into their correct buckets, sorting becomes much easier and faster.
This algorithm matters because it is commonly used when working with floating-point numbers, percentages, or normalized data such as exam scores and sensor readings. Bucket Sort is also a great learning tool because it helps beginners understand the idea of breaking a big problem into smaller, manageable parts. In this article, you will learn how to implement Bucket Sort in Lua through several complete programs, each explained in a clear and friendly way so you can confidently use it in your own projects.
Program 1: Basic Bucket Sort using loops
This program shows a simple Bucket Sort implementation in Lua using loops. It assumes that the input values are floating-point numbers between 0 and 1. This is the classic and most common way Bucket Sort is first taught.
-- Basic Bucket Sort in Lua
function bucketSort(arr)
local n = #arr
local buckets = {}
for i = 1, n do
buckets[i] = {}
end
for i = 1, n do
local index = math.floor(arr[i] * n) + 1
table.insert(buckets[index], arr[i])
end
for i = 1, n do
table.sort(buckets[i])
end
local k = 1
for i = 1, n do
for j = 1, #buckets[i] do
arr[k] = buckets[i][j]
k = k + 1
end
end
end
local values = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}
bucketSort(values)
for _, v in ipairs(values) do
io.write(v .. " ")
endThis program works by creating empty buckets and placing each number into a bucket based on its value. Each bucket is then sorted individually using Lua’s built-in sort function. Beginners can think of this as first grouping similar numbers together and then arranging them neatly inside each group.
Program 2: Bucket Sort with clearer structure
This version improves readability by separating logic into well-defined steps. It is useful for beginners who want to clearly see how bucket creation, distribution, and merging work.
-- Bucket Sort with clearer structure
function bucketSort(arr)
local bucketCount = #arr
local buckets = {}
for i = 1, bucketCount do
buckets[i] = {}
end
for _, value in ipairs(arr) do
local bucketIndex = math.floor(value * bucketCount) + 1
table.insert(buckets[bucketIndex], value)
end
local index = 1
for i = 1, bucketCount do
table.sort(buckets[i])
for _, value in ipairs(buckets[i]) do
arr[index] = value
index = index + 1
end
end
end
local data = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}
bucketSort(data)
for i = 1, #data do
print(data[i])
endThis program behaves the same as the first one but is easier to read and understand. Each step of the algorithm is clearly visible in the code. Beginners can use this structure as a template when learning or teaching Bucket Sort.
Program 3: Bucket Sort with step-by-step output
This program prints the state of the array after sorting each bucket. It helps beginners visually understand how values move from buckets back into the array.
-- Bucket Sort with step-by-step output
function bucketSort(arr)
local n = #arr
local buckets = {}
for i = 1, n do
buckets[i] = {}
end
for i = 1, n do
local index = math.floor(arr[i] * n) + 1
table.insert(buckets[index], arr[i])
end
local pos = 1
for i = 1, n do
table.sort(buckets[i])
print("Bucket " .. i .. " sorted:")
for _, v in ipairs(buckets[i]) do
io.write(v .. " ")
arr[pos] = v
pos = pos + 1
end
print()
end
-- final sorted output
print("\nFinal sorted data:")
for _, v in ipairs(arr) do
io.write(v .. " ")
end
print()
end
local sample = {0.29, 0.25, 0.3, 0.10, 0.27, 0.21}
bucketSort(sample)By printing each bucket after sorting, this program removes confusion about what happens behind the scenes. Beginners can clearly see how values are grouped and then merged. This makes Bucket Sort feel more concrete and less abstract.
Program 4: Bucket Sort for integer values in a range
This version adapts Bucket Sort to work with integers within a known range. It shows that Bucket Sort is not limited to floating-point numbers.
-- Bucket Sort for integers
function bucketSort(arr, maxValue)
local bucketCount = maxValue + 1
local buckets = {}
for i = 0, bucketCount do
buckets[i] = {}
end
for _, value in ipairs(arr) do
table.insert(buckets[value], value)
end
local index = 1
for i = 0, bucketCount do
for _, value in ipairs(buckets[i]) do
arr[index] = value
index = index + 1
end
end
end
local numbers = {4, 1, 3, 2, 3, 1, 0}
bucketSort(numbers, 4)
for _, v in ipairs(numbers) do
io.write(v .. " ")
endThis approach works well when the range of values is small and known in advance. Beginners can see how buckets can represent exact values instead of ranges. This makes Bucket Sort flexible for different types of problems.
Program 5: Bucket Sort using insertion sort inside buckets
This program replaces Lua’s built-in sort with a simple insertion sort inside each bucket. It helps beginners understand how Bucket Sort can be combined with other algorithms.
-- Bucket Sort using insertion sort inside buckets
function insertionSort(arr)
for i = 2, #arr do
local key = arr[i]
local j = i - 1
while j >= 1 and arr[j] > key do
arr[j + 1] = arr[j]
j = j - 1
end
arr[j + 1] = key
end
end
function bucketSort(arr)
local n = #arr
local buckets = {}
for i = 1, n do
buckets[i] = {}
end
for _, value in ipairs(arr) do
local index = math.floor(value * n) + 1
table.insert(buckets[index], value)
end
local k = 1
for i = 1, n do
insertionSort(buckets[i])
for _, value in ipairs(buckets[i]) do
arr[k] = value
k = k + 1
end
end
end
local values = {0.34, 0.12, 0.89, 0.45, 0.67}
bucketSort(values)
for _, v in ipairs(values) do
io.write(v .. " ")
endThis program shows that Bucket Sort does not depend on a single sorting method. Beginners learn that simple algorithms like insertion sort work well inside small buckets. This also reinforces the idea of combining algorithms to solve problems efficiently.
Program 6: Bucket Sort handling negative and floating-point numbers
By default, Bucket Sort assumes values are between 0 and 1. This final program tweaks the logic so it can handle negative numbers and general floating-point values.
-- Bucket Sort handling negative and floating-point numbers
function bucketSort(arr)
local minValue = arr[1]
local maxValue = arr[1]
for i = 2, #arr do
if arr[i] < minValue then minValue = arr[i] end
if arr[i] > maxValue then maxValue = arr[i] end
end
local bucketCount = #arr
local buckets = {}
for i = 1, bucketCount do
buckets[i] = {}
end
local range = maxValue - minValue
for _, value in ipairs(arr) do
local index = math.floor(((value - minValue) / range) * (bucketCount - 1)) + 1
table.insert(buckets[index], value)
end
local k = 1
for i = 1, bucketCount do
table.sort(buckets[i])
for _, value in ipairs(buckets[i]) do
arr[k] = value
k = k + 1
end
end
end
local mixed = {-2.5, 3.1, 0.0, -1.2, 4.8, 2.2}
bucketSort(mixed)
for _, v in ipairs(mixed) do
io.write(v .. " ")
endThis program adjusts values based on the minimum and maximum range before placing them into buckets. Beginners can see how a limitation of Bucket Sort can be solved with simple math. This makes the algorithm practical for real-world data that includes negative and decimal numbers.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Bucket Sort in Lua.
Q1. When is Bucket Sort a good choice?
Bucket Sort works best when data is evenly distributed over a known range. It is especially useful for floating-point numbers.
Q2. Is Bucket Sort faster than Quick Sort?
Bucket Sort can be faster in specific cases, but Quick Sort is more flexible and works well for general data.
Q3. Does Bucket Sort use extra memory?
Yes, Bucket Sort uses extra memory for buckets. This is the trade-off for faster sorting in the right conditions.
Q4. Can Bucket Sort handle negative numbers?
Not by default, but with small adjustments, it can handle negative and floating-point numbers as shown above.
Q5. Is Bucket Sort stable?
Bucket Sort can be stable if the sorting method used inside buckets is stable.
Conclusion
Bucket Sort is a friendly and practical sorting algorithm that shines when data is well distributed. In this article, you explored several Lua programs that implement Bucket Sort in different ways, starting from a basic version and moving toward more advanced and realistic cases. Each example was designed to help beginners understand not just the code, but also the thinking behind the algorithm.
By practicing these Lua programs and experimenting with different datasets, you can gain confidence in sorting techniques and algorithm design. Keep exploring, keep coding, and remember that understanding simple ideas like buckets can lead to powerful solutions in real-world programming.
