util.sort = {}

--- implementation of selection sort (best O(1) - avg O(n**2) - worsts O(n**2))
---
--- INFO: the nature of selection sort makes it optimal if you want to sort small to medium big arrays with high entropy
---
--- INFO: this implementation will efficiently handle already sorted and empty arrays
--- @param arr any[] input arr
--- @param i? number sorting start index. Defaults to 1
--- @param j? number sorting stop index. Defaults to #arr
--- @param compFunction? fun(a:any, b:any) function taking a (current index) and b (comparision object).
--- @param inplace? boolean array will be sorted inplace. Defaults to true
--- @return table @sorted table (eiter pointer to original or new depending on inplace setting)
function util.sort.selctSort(arr, i, j, compFunction, inplace)
    if type(arr) ~= "table" then error(util.error.argErr(arr, "table", 1)) end

    -- if not inplace => deepcopy table
    arr = not inplace and util.misc.deepCopy(arr) or arr

    -- if comparison function is not supplied or not a function set default
    compFunction = type(compFunction) == "function" and compFunction or function (a, b) return a < b end
    i, j = tonumber(i) or 1, tonumber(j) or #arr

    -- array is either empty or 1 big => already sorted
    if #arr <= 1 then return arr end

    -- check if arr is already sorted
    local curr = i
    while curr < #arr and compFunction(arr[curr], arr[curr+1]) do
        curr = curr+1
    end

    -- arr is already sorted
    if curr >= j then return arr end

    -- selection sort implementation
    for sortIndex=i, j do
        local minIndex = util.misc.getMinIndex(arr, sortIndex)

        if compFunction(arr[minIndex], arr[sortIndex]) then
            arr[sortIndex], arr[minIndex] = arr[minIndex], arr[sortIndex]
        end
    end

    return arr
end
