Counting Sort is a unique and efficient sorting algorithm that works differently from comparison-based sorts like Bubble Sort or Quick Sort. Instead of comparing elements directly, Counting Sort counts the number of times each value occurs in the array. This count is then used to place each element directly into its correct position. Because of this approach, Counting Sort can be incredibly fast for sorting integers within a limited range.
This algorithm is important for beginners to learn because it introduces the idea of non-comparison-based sorting. Counting Sort is widely used in scenarios like sorting exam scores, age groups, or any numeric data where the range of numbers is known and not too large. Understanding Counting Sort in Lua gives beginners a new perspective on how sorting can be optimized beyond simple comparisons, while also providing hands-on experience with arrays and tables in Lua.
Program 1: Basic Counting Sort for positive integers
This first program demonstrates a simple implementation of Counting Sort in Lua, suitable for arrays containing only positive integers. It is perfect for beginners to understand the basic concept.
-- Basic Counting Sort in Lua
function countingSort(arr)
local max = 0
for i = 1, #arr do
if arr[i] > max then
max = arr[i]
end
end
local count = {}
for i = 0, max do
count[i] = 0
end
for i = 1, #arr do
count[arr[i]] = count[arr[i]] + 1
end
local index = 1
for i = 0, max do
while count[i] > 0 do
arr[index] = i
index = index + 1
count[i] = count[i] - 1
end
end
end
local numbers = {4, 2, 2, 8, 3, 3, 1}
countingSort(numbers)
for _, v in ipairs(numbers) do
io.write(v .. " ")
endThis program works by first finding the largest number to define the size of the counting array. It then counts occurrences of each number and reconstructs the sorted array. Beginners can understand Counting Sort as a method that “counts first, sorts later,” which is very different from typical comparison-based approaches.
Program 2: Counting Sort with clearer structure
This version uses clear variable names and comments to make it easier for beginners to follow. The logic is the same, but readability is improved.
-- Counting Sort with clear structure
function countingSort(arr)
local n = #arr
local maxValue = 0
for i = 1, n do
if arr[i] > maxValue then
maxValue = arr[i]
end
end
local count = {}
for i = 0, maxValue do count[i] = 0 end
for i = 1, n do
count[arr[i]] = count[arr[i]] + 1
end
local position = 1
for i = 0, maxValue do
while count[i] > 0 do
arr[position] = i
position = position + 1
count[i] = count[i] - 1
end
end
end
local data = {5, 3, 1, 2, 3, 0, 2}
countingSort(data)
for _, v in ipairs(data) do
print(v)
endBy using meaningful names like position and maxValue, beginners can clearly see each step. This approach emphasizes how Counting Sort organizes and reconstructs the array using simple arithmetic.
Program 3: Counting Sort with step-by-step output
This program prints the array after counting and during reconstruction, helping beginners visualize how the algorithm progresses.
-- Counting Sort with step-by-step output
function countingSort(arr)
local maxValue = 0
for i = 1, #arr do
if arr[i] > maxValue then
maxValue = arr[i]
end
end
local count = {}
for i = 0, maxValue do count[i] = 0 end
for i = 1, #arr do
count[arr[i]] = count[arr[i]] + 1
end
print("Count array after counting occurrences:")
for i = 0, maxValue do
io.write(count[i] .. " ")
end
print()
local index = 1
for i = 0, maxValue do
while count[i] > 0 do
arr[index] = i
index = index + 1
count[i] = count[i] - 1
end
print("Array after placing " .. i .. ":")
for _, v in ipairs(arr) do io.write(v .. " ") end
print()
end
end
local sample = {4, 2, 0, 3, 2, 1}
countingSort(sample)
-- final sorted output
print("\nFinal sorted data:")
for _, v in ipairs(sample) do
io.write(v .. " ")
end
print()Seeing the intermediate states helps beginners understand that Counting Sort does not swap elements like Bubble Sort or Quick Sort. Instead, it systematically builds the sorted array, which makes it feel logical and structured.
Program 4: Counting Sort wrapped as a reusable function
This version is clean and ready to be used in other Lua programs. It demonstrates how Counting Sort can be reused without rewriting code.
-- Reusable Counting Sort function
function countingSort(arr)
local maxValue = 0
for _, v in ipairs(arr) do
if v > maxValue then
maxValue = v
end
end
local counts = {}
for i = 0, maxValue do counts[i] = 0 end
for _, v in ipairs(arr) do
counts[v] = counts[v] + 1
end
local pos = 1
for i = 0, maxValue do
while counts[i] > 0 do
arr[pos] = i
pos = pos + 1
counts[i] = counts[i] - 1
end
end
end
local numbers = {3, 6, 4, 1, 3, 4, 1, 4}
countingSort(numbers)
for _, v in ipairs(numbers) do
io.write(v .. " ")
endThis approach is practical for real projects. Beginners can use this function as a utility whenever they need to sort positive integers efficiently. It also shows how simple functions can be organized cleanly in Lua.
Program 5: Counting Sort with negative numbers
By default, Counting Sort only works for non-negative integers. This program tweaks it to handle negative numbers by shifting values into a positive range.
-- Counting Sort for negative numbers
function countingSort(arr)
local minValue, maxValue = arr[1], arr[1]
for i = 2, #arr do
if arr[i] > maxValue then maxValue = arr[i] end
if arr[i] < minValue then minValue = arr[i] end
end
local range = maxValue - minValue + 1
local count = {}
for i = 1, range do count[i] = 0 end
for i = 1, #arr do
count[arr[i] - minValue + 1] = count[arr[i] - minValue + 1] + 1
end
local index = 1
for i = 1, range do
while count[i] > 0 do
arr[index] = i + minValue - 1
index = index + 1
count[i] = count[i] - 1
end
end
end
local numbers = {-5, -10, 0, -3, 8, 5, -1, 10}
countingSort(numbers)
for _, v in ipairs(numbers) do
io.write(v .. " ")
endThis version demonstrates how Counting Sort can be adapted to work with negative numbers by using a shift. Beginners learn that algorithms can often be modified for different data, which is a valuable programming skill.
Frequently Asked Questions (FAQ)
This section answers common questions about Counting Sort in Lua.
Q1. Can Counting Sort handle floating-point numbers?
No, Counting Sort works best with integers because it relies on array indices. For decimals, values must be converted or another sorting method should be used.
Q2. Is Counting Sort faster than Quick Sort?
Counting Sort can be faster for integers in a small range because it avoids comparisons. However, for large ranges or non-integer data, Quick Sort may be better.
Q3. Is Counting Sort stable?
Yes, Counting Sort is stable if implemented carefully. Equal elements maintain their relative order.
Q4. Does Counting Sort use extra memory?
Yes, it requires extra space for the counting array, which depends on the range of input values.
Q5. When should I use Counting Sort?
Use it when sorting integers or small-range numeric data where performance is important.
Conclusion
Counting Sort is a practical and efficient algorithm for sorting integers in Lua. In this article, you explored multiple programs from basic implementations to more advanced versions handling negative numbers. Each program was designed to help beginners understand the counting approach and how arrays can be manipulated to achieve sorting efficiently.
By practicing these examples, experimenting with your own data, and modifying the functions, you can gain confidence in Lua programming and develop a deeper understanding of non-comparison-based sorting. Counting Sort teaches a valuable lesson: sometimes, the fastest solutions come from thinking differently, not just comparing values.
