| -rw-r--r-- | algorithm.lua | 166 |
diff --git a/algorithm.lua b/algorithm.lua index 3e5d5700..7f707896 100644 --- a/algorithm.lua +++ b/algorithm.lua @@ -19,10 +19,91 @@ local function less_than(a, b) return a < b end +local function lg2(a) + local c = 0 + while a > 0 do + a = rshift(a, 1) + c = c + 1 + end + return c - 1 +end + local function div2(a) return rshift(a, 1) end +local function heapsort(array, i0, i1, f) + f = f or less_than + + local function push_heap(first, hole, top, value) + local parent = div2(hole - 1) + while hole > top and f(array[first + parent], value) do + array[first + hole] = array[first + parent] + hole = parent + parent = div2(hole - 1) + end + array[first + hole] = value + end + + local function adjust_heap(first, hole, len, value) + local top = hole + local second = hole + while second < div2(len - 1) do + second = 2 * (second + 1) + if f(array[first + second], array[first + (second - 1)]) then + second = second - 1 + end + array[first + hole] = array[first + second] + hole = second + end + if band(len, 1) == 0 and second == div2(len - 2) then + second = 2 * (second + 1) + array[first + hole] = array[first + (second - 1)] + hole = second - 1 + end + push_heap(first, hole, top, value) + end + + local function pop_heap(first, last, result) + local value = array[result] + array[result] = array[first] + adjust_heap(first, 0, last - first, value) + end + + local function make_heap(first, last) + if last - first < 2 then return end + local len = last - first + local parent = div2(len - 2) + while true do + local value = array[first + parent] + adjust_heap(first, parent, len, value) + if parent == 0 then + return + end + parent = parent - 1 + end + end + + local function heap_select(first, middle, last) + make_heap(first, middle) + for i = middle, last - 1 do + if f(array[i], array[first]) then + pop_heap(first, middle, i) + end + end + end + + local function sort_heap(first, last) + while last - first > 1 do + last = last - 1 + pop_heap(first, last, last) + end + end + + heap_select(i0, i1 + 1, i1 + 1) + sort_heap(i0, i1 + 1) +end + local function insertion_sort(array, compare, istart, iend) for i = istart + 1, iend do local current_value = array[i] @@ -77,16 +158,21 @@ local function quicksort(array, i0, i1, f) return partition(first + 1, last, array[first]) end - local function quicksort_loop(first, last) + local function quicksort_loop(first, last, depth) while last - first > insertion_thresold do + if depth == 0 then + heapsort(array, first, last, f) + return + end + depth = depth - 1 local cut = partition_pivot(first, last) - quicksort_loop(cut, last) - array[first], array[first + 1] = array[first + 1], array[first] + quicksort_loop(cut, last, depth) + -- array[first], array[first + 1] = array[first + 1], array[first] last = cut - 1 end end - quicksort_loop(i0, i1) + local complete = quicksort_loop(i0, i1, 2 * lg2(i1 - i0 + 1)) insertion_sort(array, f, i0, i1) end @@ -121,77 +207,5 @@ local function quicksort_mirror(array, slave, i0, i1, f) end end -local function heapsort(array, i0, i1, f) - f = f or less_than - - local function push_heap(first, hole, top, value) - local parent = div2(hole - 1) - while hole > top and f(array[first + parent], value) do - array[first + hole] = array[first + parent] - hole = parent - parent = div2(hole - 1) - end - array[first + hole] = value - end - - local function adjust_heap(first, hole, len, value) - local top = hole - local second = hole - while second < div2(len - 1) do - second = 2 * (second + 1) - if f(array[first + second], array[first + (second - 1)]) then - second = second - 1 - end - array[first + hole] = array[first + second] - hole = second - end - if band(len, 1) == 0 and second == div2(len - 2) then - second = 2 * (second + 1) - array[first + hole] = array[first + (second - 1)] - hole = second - 1 - end - push_heap(first, hole, top, value) - end - - local function pop_heap(first, last, result) - local value = array[result] - array[result] = array[first] - adjust_heap(first, 0, last - first, value) - end - - local function make_heap(first, last) - if last - first < 2 then return end - local len = last - first - local parent = div2(len - 2) - while true do - local value = array[first + parent] - adjust_heap(first, parent, len, value) - if parent == 0 then - return - end - parent = parent - 1 - end - end - - local function heap_select(first, middle, last) - make_heap(first, middle) - for i = middle, last - 1 do - if f(array[i], array[first]) then - pop_heap(first, middle, i) - end - end - end - - local function sort_heap(first, last) - while last - first > 1 do - last = last - 1 - pop_heap(first, last, last) - end - end - - heap_select(i0, i1 + 1, i1 + 1) - sort_heap(i0, i1 + 1) -end - return {quicksort = quicksort, quicksort_mirror = quicksort_mirror, heapsort = heapsort} |