# Datastructures and Algorithms

Simple datastructures and algorithms for an enby in need.

### Sorting

#### Insertion Sort - stable - O(n^2) execution - O(1) memory

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
``````

#### Gnome Sort - stable - O(n^2) execution - O(1) memory

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
``````

#### Heap Sort - unstable - O(n log n) execution - O(1) memory

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
``````