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.