2

基本的なマージソートを書いて Lua を学ぼうとしていますが、マージソートにも慣れていないため、いくつかの問題に遭遇しました。

コード：

arr = {}
status = 0


function return_first_half (list)
    size = #list
    size = size / 2
    t = {}
    for var = 1, size, 2 do
        t[var] = list[var]
    end
    return t
end

function return_last_half (list)
    size = #list
    i = size / 2
    t = {}
    for var = size, i, -1 do
        t[var] = list[var]
    end
    return t
end


function msort (list)
    size = #list
    first_half = {}
    last_half  = {}
    if (size <= 1) then
        return list
    end
    first_half = msort(return_first_half(list))
    last_half = msort(return_last_half(list))
    if (#first_half == 1) then
        if (#last_half == 1) then
            if (first_half[1] > last_half[1]) then
                arr[status] = first_half[1]
                status = status + 1
                arr[status] = last_half[1]
                status = status + 1
            end
            if (first_half[1] < last_half[1])then
                arr[status] = last_half[1]
                status = status + 1
                arr[status] = first_half[1]
                status = status + 1
            end
        end
    end
end

function main ()
    list = {}
    for i = 1, 8, 1 do
        list[i] = io.read()
    end
    msort(list)
    for i = 1, #arr, 1 do
        print (arr[i])
    end
end

main()

入力8を1に降ろすと、nilが出力されて終了します。何か助けはありますか？

編集: 配列の長さとアドレスに関する問題を修正し、次の行でスタック オーバーフローを返すようになりました:

first_half = msort(return_first_half(list))
4

1 に答える 1

2

問題は、前半と後半を計算・コピーする際のエラーで再帰から抜け出せないことです。

ただし、始める前に、関数内の一時ストレージには常にローカル変数を使用する必要があることを指摘しておきます。これははるかに高速で、グローバル テーブルが乱雑になることもありません。実際には、グローバル変数を設定する必要があると本当に思わない限り、常に local (id に慣れてください) を使用する必要があります。

トピックに戻りreturn_first_halfます。2 つおきのアイテムをコピーします。何故ですか？不均一なテーブル サイズを許可する場合は、math.floor(size/2) も使用する必要があります。

同様にreturn_second_half。私はそれを次のように変更します：

function return_last_half (list)
    size = #list
    i = math.floor(size / 2) + 1
    t = {}
    local itemno = 1
    for var = i, size do
        t[itemno] = list[var]
    end
    return t
end

お使いのバージョンの問題:

  • テーブルサイズが不均一な場合、小数が得られます
  • 戻りテーブルの同じ位置、つまり 5、6、7、8 に項目を設定しています。つまり、サイズ#演算子は 8 を返しますが、項目の数は 4 です。実際には、配列にギャップがあるときはいつでも、サイズ演算子の動作は未定義です。

一般に、あなたのアルゴリズムはあまりうまく設計されていないので、これ以上深く掘り下げるつもりはありません。スタックオーバーフローを回避する方法を説明したので、必要に応じてそこから取得できます。

しかし、アイテムをその場でソートする (それらを同じテーブルに戻す) マージソートの簡単な実装を紹介しましょう。

local function merge(list, start, middle, stop)
    local temp = {}
    local itemno = 1
    local item1, item2 = start, middle + 1

    while item1 <= middle and item2 <= stop do
        if list[item2] < list[item1] then
            temp[itemno] = list[item2]
            item2 = item2 + 1
        else
            temp[itemno] = list[item1]
            item1 = item1 + 1
        end
        itemno = itemno + 1
    end

    if item1 <= middle then
        while item1 <= middle do
            temp[itemno] = list[item1]
            itemno = itemno + 1
            item1 = item1 + 1
        end
    else
        while item2 <= stop do
            temp[itemno] = list[item2]
            itemno = itemno + 1
            item2 = item2 + 1
        end
    end

    itemno = 1
    for i = start, stop do
        list[i] = temp[itemno]
        itemno = itemno + 1
    end
end

local function msort(list, start, stop)
    if stop - start == 0 then
        return list
    elseif start > stop then
        error("Oh crap")
    end

    local middle = math.floor((stop + start) / 2)
    msort(list, start, middle)
    msort(list, middle + 1, stop)
    merge(list, start, middle, stop)
end

local function main ()
    list = {}
    print("Enter number of items:")
    local i = tonumber(io.read())
    for item = 1, i do
        print("Enter item number " .. item .. ":")
        list[item] = tonumber(io.read())
    end
    msort(list, 1, i)
    for k, v in ipairs(list) do
        print (v)
    end
end

main()

編集：

この単純な再帰的な実装について注意すべき点は、リストが十分に大きい場合、とにかくスタック オーバーフローが発生することです。

于 2013-05-14T07:19:03.390 に答える