-- Time Complexity from O(n log(n)) to O(n^2)
-- Space Complexity O(log(n))
-- Smaller than the middle item go left, greater
-- go right, then each part is sorted the same way
local function quick_sort(data)
local items = table.move(data, 1, #data, 1, {})
local function sort_part(first, last)
if first >= last then
return
end
local i, j = first, last
local pivot = items[(first + last) // 2]
while i <= j do
while items[i] < pivot do
i = i + 1
end
while items[j] > pivot do
j = j - 1
end
if i <= j then
items[i], items[j] = items[j], items[i]
i, j = i + 1, j - 1
end
end
sort_part(first, j)
sort_part(i, last)
end
sort_part(1, #items)
return items
end
local items = {4, 1, 5, 3, 2}
local sort_items = quick_sort(items)
-- items = 4, 1, 5, 3, 2
-- sort_items = 1, 2, 3, 4, 5
print("items = " .. table.concat(items, ", "))
print("sort_items = " ..
table.concat(sort_items, ", "))
-- *** simplified speed test ***
items = {}
for n = 1, 199 do
items[n] = n
end
items[6], items[7] = items[7], items[6]
local count = 1000
local start = os.clock()
for _ = 1, count do
quick_sort(items)
end
local total_ms = (os.clock() - start) * 1000
-- The time depends on the machine
print(string.format("total_ms = %.2f", total_ms))