Quick Sort is one of the most popular and powerful sorting algorithms used in programming today. The idea behind Quick Sort is to pick a value called a pivot, place it in its correct position, and then arrange all smaller values to one side and larger values to the other side. This process repeats again and again until the entire list is sorted. Even though the idea sounds simple, Quick Sort is very fast and efficient in most real situations.
In Lua programming, learning Quick Sort is important because it teaches you how recursion, partitioning, and problem solving work together. Quick Sort is widely used in real systems like databases, search engines, and operating systems because it performs well on large data sets. For beginners, understanding Quick Sort helps build strong algorithm thinking and prepares you for more advanced programming topics.
Program 1: Basic Recursive Quick Sort in Lua
This program shows the most classic way to implement Quick Sort using recursion. It picks a pivot and sorts the remaining values around it.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[1]
local left = {}
local right = {}
for i = 2, #arr do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
local result = {}
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {10, 7, 8, 9, 1, 5}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endThis code works by breaking the table into smaller parts based on the pivot value. Each part is sorted separately and then combined. Beginners can understand this by thinking of Quick Sort as organizing items around a chosen center point.
Program 2: Quick Sort Using Last Element as Pivot
This program chooses the last element as the pivot instead of the first. This shows that the pivot choice can change without breaking the algorithm.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[#arr]
local left = {}
local right = {}
for i = 1, #arr - 1 do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {4, 2, 6, 9, 2}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endThis version helps beginners see that Quick Sort is flexible. The main idea is partitioning, not the exact position of the pivot. Understanding this makes the algorithm less confusing.
Program 3: In-Place Quick Sort Using Indexes
This program sorts the table in place without creating many new tables. It is closer to how Quick Sort is used in real applications.
local function partition(arr, low, high)
local pivot = arr[high]
local i = low - 1
for j = low, high - 1 do
if arr[j] <= pivot then
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
end
end
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
end
local function quickSort(arr, low, high)
if low < high then
local pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
end
end
local numbers = {3, 6, 8, 10, 1, 2, 1}
quickSort(numbers, 1, #numbers)
for i = 1, #numbers do
print(numbers[i])
endThis approach uses indexes instead of extra tables, which saves memory. Beginners learn how swapping and indexing work together. This style is important for performance-focused Lua programs.
Program 4: Quick Sort with Step-by-Step Output
This program prints the table during sorting so you can see how values move around the pivot.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[1]
local left = {}
local right = {}
for i = 2, #arr do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
left = quickSort(left)
right = quickSort(right)
local result = {}
for i = 1, #left do
result[#result + 1] = left[i]
end
result[#result + 1] = pivot
for i = 1, #right do
result[#result + 1] = right[i]
end
-- print steps
for i = 1, #result do
io.write(result[i] .. " ")
end
print()
return result
end
local numbers = {8, 5, 3, 7, 4, 0, 6, 2, 9, 1}
local sorted = quickSort(numbers)Seeing intermediate steps helps beginners understand how Quick Sort works internally. It makes the algorithm feel more visual and less abstract.
Program 5: Quick Sort Wrapped Inside a Reusable Function
This program focuses on clean and reusable design. The sorting logic is placed inside a function.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[math.floor(#arr / 2)]
local left = {}
local equal = {}
local right = {}
for i = 1, #arr do
if arr[i] < pivot then
left[#left + 1] = arr[i]
elseif arr[i] > pivot then
right[#right + 1] = arr[i]
else
equal[#equal + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
for i = 1, #equal do
result[#result + 1] = equal[i]
end
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {4, 5, 3, 7, 2, 2, 8}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endThis version handles duplicate values neatly and keeps the code clean. Beginners can learn good structure and reuse this function in many projects.
Program 6: Quick Sort for String Values
Quick Sort also works well with text data. This program sorts strings alphabetically.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[1]
local left = {}
local right = {}
for i = 2, #arr do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local words = {"lua", "python", "c", "java", "ruby"}
local sorted = quickSort(words)
for i = 1, #sorted do
print(sorted[i])
endLua compares strings naturally, so Quick Sort does not need extra logic. This example shows that the same algorithm works for both numbers and text.
Program 7: Quick Sort with Descending Order
This program modifies Quick Sort to sort values from largest to smallest.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[1]
local left = {}
local right = {}
for i = 2, #arr do
if arr[i] > pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {3, 1, 4, 1, 5, 9}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endThis example shows how easy it is to change the sorting order. Beginners can learn how comparisons control the final result.
Program 8: Quick Sort as a Utility Function
This version focuses on making Quick Sort easy to reuse in different Lua programs.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[#arr]
local left = {}
local right = {}
for i = 1, #arr - 1 do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {11, 7, 3, 9, 2}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endThis clean design helps beginners build reusable code. It is suitable for small tools and learning projects.
Program 9: Quick Sort with Negative and Floating Point Numbers
Quick Sort naturally supports negative and floating point numbers. This program clearly shows that behavior.
local function quickSort(arr)
if #arr <= 1 then
return arr
end
local pivot = arr[1]
local left = {}
local right = {}
for i = 2, #arr do
if arr[i] < pivot then
left[#left + 1] = arr[i]
else
right[#right + 1] = arr[i]
end
end
local result = {}
local sortedLeft = quickSort(left)
local sortedRight = quickSort(right)
for i = 1, #sortedLeft do
result[#result + 1] = sortedLeft[i]
end
result[#result + 1] = pivot
for i = 1, #sortedRight do
result[#result + 1] = sortedRight[i]
end
return result
end
local numbers = {3.5, -2.1, 4.8, 0, -6.3}
local sorted = quickSort(numbers)
for i = 1, #sorted do
print(sorted[i])
endLua compares numbers naturally, so no changes are needed. This confirms that Quick Sort works well with real-world numeric data.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Quick Sort in Lua.
Q1. Why is Quick Sort faster than many other sorting algorithms?
Quick Sort reduces the problem size quickly by partitioning the data, which makes it very efficient in practice.
Q2. Is Quick Sort always the fastest?
Quick Sort is usually fast, but in rare cases it can be slow if the pivot choice is poor.
Q3. Does Quick Sort use extra memory?
Some versions use extra memory for new tables, while in-place versions use much less memory.
Q4. Does Lua provide a built-in sorting function?
Yes, Lua offers table.sort, but learning Quick Sort helps you understand how sorting works internally.
Conclusion
Quick Sort is a fast, flexible, and powerful sorting algorithm that is widely used in real-world systems. In this article, you explored many Lua programs that implement Quick Sort using recursion, in-place logic, reusable functions, and different data types. You also saw how it works with strings, duplicate values, negative numbers, and floating point values.
Although Quick Sort may feel complex at first, regular practice makes it easier. Try changing the pivot, printing intermediate steps, or sorting different kinds of data. With time and hands-on experience, Quick Sort will become an important part of your Lua programming skills.
