2

だから私はPythonでこの単純なマージとソートのアルゴリズムを理解しようとしています。コードは次のとおりです。

def merge(left, right, lt):
    """Assumes left and right are sorted lists.

    lt defines an ordering on the elements of the lists.
    Returns a new sorted(by lt) list containing the same elements
    as (left + right) would contain.

    """
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
       if lt(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        while (i < len(left)):
            result.append(left[i])
            i += 1
        while (j < len(right)):
            result.append(right[j])
            j += 1
    return result

def sort(L, lt = lambda x,y: x < y):
    """Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = sort(L[:middle], lt)
        right = sort(L[middle:], lt)
        print left, right
        return merge(left, right, lt)

私はそれがやろうとしていることを理解し、マージ関数のすべてのコードを理解し、ソート関数の基本的な理解を持っています。

私が理解していないのは、ソート関数の「else」部分が実際にどのように機能するかです。ソート関数を再帰的に呼び出して、左右の変数にますます小さな分割リストを割り当てているようです。しかし、再帰関数を呼び出すたびに新しいリストが「左」と「右」に割り当てられるため、最終結果は左と右の最小バージョンになるのではないでしょうか。

再帰の外側にあるように見えるマージ関数は、作成されたすべての分割リストをマージする必要があることをどのように認識しますか？

4

2 に答える 2

6

sort()再帰的ですが、ある程度までです。のif長さがlist2未満（または1に等しい）になると、条件は再帰を中断します。

if len(L) < 2:

ウィキペディアには、実際には、マージソートがどのように機能するかを示す素晴らしいアニメーションがあります。

ここに画像の説明を入力してください

基本的にmerge()、2つの並べ替えられたリストを組み合わせて、1つの並べ替えられたリストを返します。sort()リストを再帰的にペアに分割し、ペアを一度に1ステップずつ並べ替え、2つの並べ替えられたペアをマージして、再帰のすべてのステップでより大きな並べ替えリストを形成します。アニメーションを見てください。私よりも説明が上手です。

于 2012-09-20T19:55:15.390 に答える
3

コールスタックを引き出して、何が起こるかを確認する必要があります。

else句がsort関数を再度呼び出すと、関数はそこで終了しません。すべての呼び出しは、returnステートメントの1つで終了します。

sortしたがって、最初はへの呼び出しがますます小さなリストで渡されるのは正しいですが、長さが2未満になると、「sort」はリスト自体を返します。次に、呼び出しは元の場所に戻りprint、最後に呼び出しますmerge。

小さなリストを使用して、すべての呼び出しを書き留めてみてください。mergeソートされた小さなリストで最終的に呼び出されることがわかります（リストが非常に短いため）。

于 2012-09-20T19:56:30.440 に答える