-- Time Complexity O(n^2)
-- Space Complexity O(1)
-- Neighbours change places until a pass makes
-- no swaps: the largest item bubbles up
-- to the end
local function bubble_sort(data)
local items = table.move(data, 1, #data, 1, {})
for last = #items, 2, -1 do
local swapped = false
for j = 2, last do
if items[j] < items[j - 1] then
-- Swap without a temporary variable
items[j - 1], items[j] =
items[j], items[j - 1]
swapped = true
end
end
if not swapped then
break
end
end
return items
end
local items = {4, 1, 5, 3, 2}
local sort_items = bubble_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] = 200 - n
end
local count = 100
local start = os.clock()
for _ = 1, count do
bubble_sort(items)
end
local total_ms = (os.clock() - start) * 1000
-- The time depends on the machine
print(string.format("total_ms = %.2f", total_ms))