All sorting algorithms module
local module = {}
function module.Bubble(t)
local t2 = {}
for i = 1, #t do
t2[i] = t[i]
end
for i = 1, #t2 do
for j = 1, #t2 - 1 do
if t2[j] > t2[j + 1] then
t2[j], t2[j + 1] = t2[j + 1], t2[j]
end
end
end
return t2
end
function module.Selection(arr)
local len = #arr
for i = 1, len - 1 do
local min = i
for j = i + 1, len do
if arr[j] < arr[min] then
min = j
end
end
if min ~= i then
arr[i], arr[min] = arr[min], arr[i]
end
end
return arr
end
function module.Insertion(array)
for i = 2, #array do
local key = array[i]
local j = i - 1
while j > 0 and array[j] > key do
array[j + 1] = array[j]
j = j - 1
end
array[j + 1] = key
end
return array
end
local function merge(left, right)
local result = {}
local i = 1
local j = 1
while i <= #left and j <= #right do
if left[i] <= right[j] then
result[#result + 1] = left[i]
i = i + 1
else
result[#result + 1] = right[j]
j = j + 1
end
end
while i <= #left do
result[#result + 1] = left[i]
i = i + 1
end
while j <= #right do
result[#result + 1] = right[j]
j = j + 1
end
return result
end
local function mergeSort(array)
if #array > 1 then
local middle = math.floor(#array / 2)
local left = {}
local right = {}
for i = 1, middle do
left[i] = array[i]
end
for i = middle + 1, #array do
right[i - middle] = array[i]
end
left = mergeSort(left)
right = mergeSort(right)
array = merge(left, right)
end
return array
end
function module.Merge(array)
if #array > 1 then
local middle = math.floor(#array / 2)
local left = {}
local right = {}
for i = 1, middle do
left[i] = array[i]
end
for i = middle + 1, #array do
right[i - middle] = array[i]
end
left = mergeSort(left)
right = mergeSort(right)
array = merge(left, right)
end
return array
end
local function partition(arr, left, right)
local pivot = arr[math.floor((left + right) / 2)]
local i = left
local j = right
while i <= j do
while arr[i] < pivot do
i = i + 1
end
while arr[j] > pivot do
j = j - 1
end
if i <= j then
arr[i], arr[j] = arr[j], arr[i]
i = i + 1
j = j - 1
end
end
return i
end
local function quickSort(arr, left, right)
local index = partition(arr, left, right)
if left < index - 1 then
quickSort(arr, left, index - 1)
end
if index < right then
quickSort(arr, index, right)
end
end
function module.Quick(arr, left, right)
local index = partition(arr, left, right)
if left < index - 1 then
quickSort(arr, left, index - 1)
end
if index < right then
quickSort(arr, index, right)
end
return
end
function module.Counting(array, k)
local count = {}
local result = {}
for i = 1, k do
count[i] = 0
end
for i = 1, #array do
count[array[i]] = count[array[i]] + 1
end
for i = 2, k do
count[i] = count[i] + count[i - 1]
end
for i = #array, 1, -1 do
result[count[array[i]]] = array[i]
count[array[i]] = count[array[i]] - 1
end
return result
end
function module.Radix(t)
local max = 0
for i = 1, #t do
if t[i] > max then
max = t[i]
end
end
local exp = 1
while max / exp > 1 do
local buckets = {}
for i = 0, 9 do
buckets[i] = {}
end
for i = 1, #t do
local digit = math.floor(t[i] / exp) % 10
table.insert(buckets[digit], t[i])
end
local index = 1
for i = 0, 9 do
for j = 1, #buckets[i] do
t[index] = buckets[i][j]
index = index + 1
end
end
exp = exp * 10
end
return t
end
function module.Heap(arr)
local function heapify(arr, n, i)
local largest = i
local l = 2 * i + 1
local r = 2 * i + 2
if l < n and arr[l] > arr[largest] then
largest = l
end
if r < n and arr[r] > arr[largest] then
largest = r
end
if largest ~= i then
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
end
end
local function heapSort(arr)
local n = #arr
for i = n, 1, -1 do
heapify(arr, n, i)
end
for i = n, 2, -1 do
arr[i], arr[1] = arr[1], arr[i]
heapify(arr, i - 1, 1)
end
end
heapSort(arr)
end
return module