LuaExample3

-- Hi Vanessa Here. I implemented and compared different sorting algorithms using 3 main ones. quicksort, mergesort, and heapsort, in terms of performance.
-- array
local function printArray(arr)
    for _, num in ipairs(arr) do
        io.write(num .. " ")
    end
    print()
end

-- quicksort implementation
local function partition(arr, low, high)
    local pivot = arr[high]
    local i = low - 1
    for j = low, high - 1 do
        if arr[j] < pivot then
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
end

local function quicksort(arr, low, high)
    if low < high then
        local pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)
    end
end

-- mergesort implementation
local function merge(arr, left, mid, right)
    local n1 = mid - left + 1
    local n2 = right - mid
    local L, R = {}, {}

    for i = 1, n1 do
        L[i] = arr[left + i - 1]
    end
    for j = 1, n2 do
        R[j] = arr[mid + j]
    end

    local i, j, k = 1, 1, left
    while i <= n1 and j <= n2 do
        if L[i] <= R[j] then
            arr[k] = L[i]
            i = i + 1
        else
            arr[k] = R[j]
            j = j + 1
        end
        k = k + 1
    end

    while i <= n1 do
        arr[k] = L[i]
        i = i + 1
        k = k + 1
    end

    while j <= n2 do
        arr[k] = R[j]
        j = j + 1
        k = k + 1
    end
end

local function mergesort(arr, left, right)
    if left < right then
        local mid = left + math.floor((right - left) / 2)
        mergesort(arr, left, mid)
        mergesort(arr, mid + 1, right)
        merge(arr, left, mid, right)
    end
end

-- heapsort implementation
local function heapify(arr, n, i)
    local largest = i
    local left = 2 * i + 1
    local right = 2 * i + 2

    if left < n and arr[left + 1] > arr[largest + 1] then
        largest = left
    end

    if right < n and arr[right + 1] > arr[largest + 1] then
        largest = right
    end

    if largest ~= i then
        arr[i + 1], arr[largest + 1] = arr[largest + 1], arr[i + 1]
        heapify(arr, n, largest)
    end
end

local function heapsort(arr)
    local n = #arr
    for i = math.floor(n / 2) - 1, 0, -1 do
        heapify(arr, n, i)
    end

    for i = n - 1, 1, -1 do
        arr[1], arr[i + 1] = arr[i + 1], arr[1]
        heapify(arr, i, 0)
    end
end

-- function to measure and compare sorting times
local function compareSorts(arr)
    local arr1 = {table.unpack(arr)}
    local arr2 = {table.unpack(arr)}
    local arr3 = {table.unpack(arr)}

    local start = os.clock()
    quicksort(arr1, 1, #arr1)
    local quicksortTime = os.clock() - start
    print("Quicksort time: " .. quicksortTime .. " seconds")

    start = os.clock()
    mergesort(arr2, 1, #arr2)
    local mergesortTime = os.clock() - start
    print("Mergesort time: " .. mergesortTime .. " seconds")

    start = os.clock()
    heapsort(arr3)
    local heapsortTime = os.clock() - start
    print("Heapsort time: " .. heapsortTime .. " seconds")
end

-- main function
local arr = {12, 11, 13, 5, 6, 7}
print("Original array: ")
printArray(arr)

compareSorts(arr)