python - ダミーのためのマージソートの説明

Question

このコードをオンラインで見つけました：

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

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

実行すると100％動作します。マージソートがどのように機能するか、または再帰関数が左と右の両方を適切に順序付ける方法が実際にはわかりません。

Answer 1

マージソートを理解する鍵は、次の原則を理解することだと私は信じています - 私はそれをマージ原則と呼びます:

最小から最大の順に並べられた 2 つの別個のリスト A と B が与えられた場合、A の最小値と B の最小値を繰り返し比較し、小さい方の値を削除して、C に追加することにより、リスト C を作成します。他のリストの残りの項目を順番に C に移動します。リスト C もソートされたリストです。

これを数回手で計算すると、それが正しいことがわかります。例えば：

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

A が使い果たされたので、B の残りの値で C を拡張します。

C = 1, 2, 3, 4

マージの原理も簡単に証明できます。A の最小値は A の他のすべての値よりも小さく、B の最小値は B の他のすべての値よりも小さくなります。A の最小値が B の最小値より小さい場合、それも小さくなければなりません。 B のすべての値よりも小さい。したがって、A のすべての値および B のすべての値より小さい。

したがって、これらの基準を満たす値を C に追加し続ける限り、ソートされたリストが得られます。これは、merge上記の関数が行うことです。

さて、この原則を考えると、リストを小さなリストに分割し、それらのリストをソートし、それらのソートされたリストをマージすることによってリストをソートするソート手法を理解するのは非常に簡単です。このmerge_sort関数は、リストを半分に分割し、それらの 2 つのリストを並べ替えてから、上記の方法でそれらの 2 つのリストをマージする単純な関数です。

唯一の問題は、再帰的であるため、2 つのサブリストをソートするときに、それらを自分自身に渡すことです! ここで再帰を理解するのが難しい場合は、まず簡単な問題を勉強することをお勧めします。しかし、再帰の基本をすでに理解している場合は、1 項目のリストが既にソートされていることだけを理解する必要があります。2 つの 1 項目リストをマージすると、ソートされた 2 項目リストが生成されます。2 つの項目からなるリストを 2 つマージすると、並べ替えられた 4 つの項目からなるリストが生成されます。等々。

Answer 2

アルゴリズムがどのように機能するかを理解するのが難しい場合は、デバッグ出力を追加して、アルゴリズム内で実際に何が起こっているかを確認します。

ここにデバッグ出力のあるコードがあります。の再帰呼び出しを使用してすべてのステップを理解し、出力がmergesortどうなるかを理解してください。merge

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
        if left[i] <= right[j]:
            print('Appending {} to the result'.format(left[i]))           
            result.append(left[i])
            print('result now is {}'.format(result))
            i += 1
            print('i now is {}'.format(i))
        else:
            print('Appending {} to the result'.format(right[j]))
            result.append(right[j])
            print('result now is {}'.format(result))
            j += 1
            print('j now is {}'.format(j))
    print('One of the list is exhausted. Adding the rest of one of the lists.')
    result += left[i:]
    result += right[j:]
    print('result now is {}'.format(result))
    return result

def mergesort(L):
    print('---')
    print('mergesort on {}'.format(L))
    if len(L) < 2:
        print('length is 1: returning the list withouth changing')
        return L
    middle = len(L) / 2
    print('calling mergesort on {}'.format(L[:middle]))
    left = mergesort(L[:middle])
    print('calling mergesort on {}'.format(L[middle:]))
    right = mergesort(L[middle:])
    print('Merging left: {} and right: {}'.format(left,right))
    out = merge(left, right)
    print('exiting mergesort on {}'.format(L))
    print('#---')
    return out


mergesort([6,5,4,3,2,1])

出力：

---
mergesort on [6, 5, 4, 3, 2, 1]
calling mergesort on [6, 5, 4]
---
mergesort on [6, 5, 4]
calling mergesort on [6]
---
mergesort on [6]
length is 1: returning the list withouth changing
calling mergesort on [5, 4]
---
mergesort on [5, 4]
calling mergesort on [5]
---
mergesort on [5]
length is 1: returning the list withouth changing
calling mergesort on [4]
---
mergesort on [4]
length is 1: returning the list withouth changing
Merging left: [5] and right: [4]
left[i]: 5 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5]
exiting mergesort on [5, 4]
#---
Merging left: [6] and right: [4, 5]
left[i]: 6 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
left[i]: 6 right[j]: 5
Appending 5 to the result
result now is [4, 5]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5, 6]
exiting mergesort on [6, 5, 4]
#---
calling mergesort on [3, 2, 1]
---
mergesort on [3, 2, 1]
calling mergesort on [3]
---
mergesort on [3]
length is 1: returning the list withouth changing
calling mergesort on [2, 1]
---
mergesort on [2, 1]
calling mergesort on [2]
---
mergesort on [2]
length is 1: returning the list withouth changing
calling mergesort on [1]
---
mergesort on [1]
length is 1: returning the list withouth changing
Merging left: [2] and right: [1]
left[i]: 2 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2]
exiting mergesort on [2, 1]
#---
Merging left: [3] and right: [1, 2]
left[i]: 3 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 3 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3]
exiting mergesort on [3, 2, 1]
#---
Merging left: [4, 5, 6] and right: [1, 2, 3]
left[i]: 4 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 4 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
left[i]: 4 right[j]: 3
Appending 3 to the result
result now is [1, 2, 3]
j now is 3
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3, 4, 5, 6]
exiting mergesort on [6, 5, 4, 3, 2, 1]
#---

Answer 3

これを理解するには、いくつかの方法があります。

デバッガーでコードをステップ実行し、何が起こるかを確認します。または、紙の上で（非常に小さな例で）ステップスルーし、何が起こるかを見てください.

（個人的には、この種のことを紙の上で行う方が有益だと思います）

概念的には、次のように機能します。入力リストは、半分になることによって、どんどん小さな断片に切り刻まれ続けます (たとえばlist[:middle]、前半です)。それぞれの半分は、長さが 2 未満になるまで何度も半分にされます。つまり、何もないか、1 つの要素になるまでです。これらの個々の部分は、2 つのサブリストをリストに追加またはインターリーブすることにより、マージ ルーチンによって元に戻されるresultため、ソートされたリストが得られます。2 つのサブリストを並べ替える必要があるため、追加/インターリーブは高速 ( O(n) ) 操作です。

これ (私の見解では) の鍵はマージ ルーチンではありません。マージ ルーチンへの入力が常にソートされることを理解すれば、それは明らかです。「トリック」(これはトリックではなく、コンピューター サイエンスなので引用符を使用します:-) ) は、マージする入力がソートされることを保証するために、ソートする必要があるリストに到達するまで再帰を続けなければならないことです。 、それがmergesort、リストの長さが 2 要素未満になるまで再帰的に呼び出し続ける理由です。

再帰、およびその拡張によるマージ ソートは、最初に遭遇したときには自明ではない場合があります。優れたアルゴリズムの本を参照することをお勧めします (たとえば、 DPVはオンラインで合法的に無料で入手できます) が、手元にあるコードをステップ実行することで、長い道のりを歩むことができます。もしあなたが本当にそれに参加したいのであれば、Stanford/Courseraアルゴ コースが間もなく再開され、彼は Merge ソートを詳細にカバーしています。

本当に理解したい場合は、その参考書の第 2 章を読んでから、上記のコードを破棄して、最初から書き直してください。真剣に。

Answer 4

マージソートは、常に私のお気に入りのアルゴリズムの 1 つです。

短い並べ替えられたシーケンスから始めて、それらを順番にマージして、より大きな並べ替えられたシーケンスにします。とても簡単。

再帰部分とは、逆方向に作業していることを意味します - シーケンス全体から始めて、2 つの半分を並べ替えます。シーケンスに要素が 0 または 1 つしかない場合に並べ替えが自明になるまで、各半分も分割されます。再帰関数が戻ると、最初の説明で述べたように、並べ替えられたシーケンスが大きくなります。

Answer 5

絵は千の言葉に値し、アニメーションは千の言葉に値する。

マージソートアルゴリズムが実際にどのように機能するかを視覚化するのに役立つ、ウィキペディアから取得した次のアニメーションを確認してください。

好奇心旺盛な人のために、分類プロセスの各ステップの説明付きの詳細なアニメーション。

さまざまな種類の並べ替えアルゴリズムの別の興味深いアニメーション。

Answer 6

ウィキペディアの記事で説明されているように、マージ ソートを実行するには多くの有益な方法があります。マージを達成する方法は、マージされるもののコレクションにも依存します。特定のコレクションは、コレクションが自由に使用できる特定のツールを有効にします。

Python を使ってこの質問に答えるつもりはありません。単に書くことができないからです。ただし、「マージソート」アルゴリズムに参加することは、全体として、問題の中心にあるようです。私を助けてくれたリソースは、アルゴリズムに関する KITE のかなり古いWeb ページ(教授によって書かれました) です。これは、コンテンツの作成者がコンテキストを意味する識別子を削除しているためです。

私の答えは、このリソースから導き出されました。

マージ ソート アルゴリズムは、提供されたコレクションを分解し、個々の断片を再び組み合わせて、コレクションが再構築されるときに断片を相互に比較することで機能することを覚えておいてください。

ここに「コード」があります（Java「フィドル」の最後を見てください）：

public class MergeSort {

/**
 * @param a     the array to divide
 * @param low   the low INDEX of the array
 * @param high  the high INDEX of the array
 */
public void divide (int[] a, int low, int high, String hilo) {


    /* The if statement, here, determines whether the array has at least two elements (more than one element). The
     * "low" and "high" variables are derived from the bounds of the array "a". So, at the first call, this if 
     * statement will evaluate to true; however, as we continue to divide the array and derive our bounds from the 
     * continually divided array, our bounds will become smaller until we can no longer divide our array (the array 
     * has one element). At this point, the "low" (beginning) and "high" (end) will be the same. And further calls 
     * to the method will immediately return. 
     * 
     * Upon return of control, the call stack is traversed, upward, and the subsequent calls to merge are made as each 
     * merge-eligible call to divide() resolves
     */
    if (low < high) {
        String source = hilo;
        // We now know that we can further divide our array into two equal parts, so we continue to prepare for the division 
        // of the array. REMEMBER, as we progress in the divide function, we are dealing with indexes (positions)

        /* Though the next statement is simple arithmetic, understanding the logic of the statement is integral. Remember, 
         * at this juncture, we know that the array has more than one element; therefore, we want to find the middle of the 
         * array so that we can continue to "divide and conquer" the remaining elements. When two elements are left, the
         * result of the evaluation will be "1". And the element in the first position [0] will be taken as one array and the
         * element at the remaining position [1] will be taken as another, separate array.
         */
        int middle = (low + high) / 2;

        divide(a, low, middle, "low");
        divide(a, middle + 1, high, "high");


        /* Remember, this is only called by those recursive iterations where the if statement evaluated to true. 
         * The call to merge() is only resolved after program control has been handed back to the calling method. 
         */
        merge(a, low, middle, high, source);
    }
}


public void merge (int a[], int low, int middle, int high, String source) {
// Merge, here, is not driven by tiny, "instantiated" sub-arrays. Rather, merge is driven by the indexes of the 
// values in the starting array, itself. Remember, we are organizing the array, itself, and are (obviously
// using the values contained within it. These indexes, as you will see, are all we need to complete the sort.  

    /* Using the respective indexes, we figure out how many elements are contained in each half. In this 
     * implementation, we will always have a half as the only way that merge can be called is if two
     * or more elements of the array are in question. We also create to "temporary" arrays for the 
     * storage of the larger array's elements so we can "play" with them and not propogate our 
     * changes until we are done. 
     */
    int first_half_element_no       = middle - low + 1;
    int second_half_element_no      = high - middle;
    int[] first_half                = new int[first_half_element_no];
    int[] second_half               = new int[second_half_element_no];

    // Here, we extract the elements. 
    for (int i = 0; i < first_half_element_no; i++) {  
        first_half[i] = a[low + i]; 
    }

    for (int i = 0; i < second_half_element_no; i++) {  
        second_half[i] = a[middle + i + 1]; // extract the elements from a
    }

    int current_first_half_index = 0;
    int current_second_half_index = 0;
    int k = low;


    while (current_first_half_index < first_half_element_no || current_second_half_index < second_half_element_no) {

        if (current_first_half_index >= first_half_element_no) {
            a[k++] = second_half[current_second_half_index++];
            continue;
        }

        if (current_second_half_index >= second_half_element_no) {
            a[k++] = first_half[current_first_half_index++];
            continue;
        }

        if (first_half[current_first_half_index] < second_half[current_second_half_index]) {
            a[k++] = first_half[current_first_half_index++];
        } else {
            a[k++] = second_half[current_second_half_index++];
        }
    }
}

また、役立つ情報を出力し、上記で何が起こっているかをより視覚的に表現するバージョンも用意しました。シンタックス ハイライトも役に立ちます。

Answer 7

ここで、マージソートがどのように機能するかをよく視覚化できます。

http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

お役に立てば幸いです。

Answer 8

基本的にはリストを取得し、それを分割してから並べ替えますが、この方法を再帰的に適用するため、簡単に並べ替えることができる簡単なセットが得られるまで何度も分割し、すべての単純なソリューションをマージして、完全にソートされた配列を取得します。