Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(Sorting algorithms/Insertion sort en Yabasic) |
|||
Line 2,474: | Line 2,474: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Binary variation of Insertion sort (Has better complexity) |
|||
<lang lua>do |
|||
local function lower_bound(container, container_begin, container_end, value, comparator) |
|||
local count = container_end - container_begin + 1 |
|||
while count > 0 do |
|||
local half = bit.rshift(count, 1) -- or math.floor(count / 2) |
|||
local middle = container_begin + half |
|||
if comparator(container[middle], value) then |
|||
container_begin = middle + 1 |
|||
count = count - half - 1 |
|||
else |
|||
count = half |
|||
end |
|||
end |
|||
return container_begin |
|||
end |
|||
local function binary_insertion_sort_impl(container, comparator) |
|||
for i = 2, #container do |
|||
local j = i - 1 |
|||
local selected = container[i] |
|||
local loc = lower_bound(container, 1, j, selected, comparator) |
|||
while j >= loc do |
|||
container[j + 1] = container[j] |
|||
j = j - 1 |
|||
end |
|||
container[j + 1] = selected |
|||
end |
|||
end |
|||
local function binary_insertion_sort_comparator(a, b) |
|||
return a < b |
|||
end |
|||
function table.bininsertionsort(container, comparator) |
|||
if not comparator then |
|||
comparator = binary_insertion_sort_comparator |
|||
end |
|||
binary_insertion_sort_impl(container, comparator) |
|||
end |
|||
end</lang> |
|||
<lang lua>function bins(tb, val, st, en) |
<lang lua>function bins(tb, val, st, en) |