Simple datastructures and algorithms for an enby in need.
Simple sorting algorithm. Probably more branch-predictor friendly than gnome sort.
--[[
`compare()` is a function that returns 0 when a == b, a negative value when a < b,
or a positive value when a > b.
If you want to use it for 0-indexed arrays,
- iterate `i` from 0 to length of xs - 1
- iterate `while j > 0`.
]]
local function insertion_sort(xs, compare)
for i = 1, #xs do
local j = i
while j > 1 and compare(xs[j - 1], xs[j]) > 0 do
local tmp = xs[j - 1]
xs[j - 1] = xs[j]
xs[j] = tmp
j = j - 1
end
end
end
Simple sorting algorithm. Requires a single index variable, while insertion sort requires 2.
--[[
`compare()` is a function that returns 0 when a == b, a negative value when a < b,
or a positive value when a > b.
If you want to use it for 0-indexed arrays,
- initialize `i` with 0
- iterate while i < #xs
- change `i == 1` to `i == 0`
]]
local function gnome_sort(xs, compare)
local i = 1
while i <= #xs do
if i == 1 or compare(xs[i], xs[i - 1]) >= 0 then
i = i + 1
else
local tmp = xs[i - 1]
xs[i - 1] = xs[i]
xs[i] = tmp
i = i - 1
end
end
end
A good O(n log n) algorithm. Runs in constant space. I also like that it’s based on a heap, since it’s a pretty common datastructure, so if you understand this algorithm you understand heaps too.
impl TODO