24

私が目にするマージソートの実装のほとんどは、これに似ています。私が探しているオンラインの実装と一緒に、アルゴリズムの本への紹介。私の再帰チョップは、フィボナッチ生成をいじるよりもはるかに進んでいないので（これは十分に単純でした）、複数の再帰が私の心を吹き飛ばしているのかもしれませんが、コードをステップ実行することさえできず、ヒットする前に何が起こっているのか理解できませんマージ機能。

これをどのように進めていますか？ここでのプロセスをよりよく理解するために、私が受けるべき戦略や読書はありますか?

void mergesort(int *a, int*b, int low, int high)
{
    int pivot;
    if(low<high)
    {
        pivot=(low+high)/2;
        mergesort(a,b,low,pivot);
        mergesort(a,b,pivot+1,high);
        merge(a,b,low,pivot,high);
    }
}

そしてマージ（率直に言って、この部分にたどり着く前に精神的に立ち往生しています）

void merge(int *a, int *b, int low, int pivot, int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=pivot+1;

    while((h<=pivot)&&(j<=high))
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    else
    {
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) a[k]=b[k];
}
4

10 に答える 10

9

明らかなことは、このマージソートを小さな配列、たとえばサイズ 8 (ここでは 2 の累乗が便利です) の紙の上で試すことです。あなたがコードを実行しているコンピューターであると仮定して、コードが少し明確になり始めるかどうかを確認してください。

わかりにくいことを説明していないため、質問は少しあいまいですが、頭の中で再帰呼び出しを展開しようとしているようです。これは良いことかもしれないし、そうでないことかもしれませんが、一度に頭の中で物事を考えすぎてしまう可能性があると思います. コードを最初から最後までトレースしようとするのではなく、概念を抽象的に理解できるかどうかを確認してください。マージソート:

  1. 配列を半分に分割します
  2. 左半分をソートします
  3. 右半分をソートします
  4. 2 つの半分を一緒にマージします

(1) はかなり明白で、直感的に理解できるはずです。ステップ（2）の重要な洞察はこれです。配列の左半分...は配列です。マージソートが機能すると仮定すると、配列の左半分をソートできるはずです。右？ステップ (4) は、実際にはアルゴリズムの非常に直感的な部分です。例はそれを簡単にするはずです:

at the start
left: [1, 3, 5], right: [2, 4, 6, 7], out: []

after step 1
left: [3, 5], right: [2, 4, 6, 7], out: [1]

after step 2
left: [3, 5], right: [4, 6, 7], out: [1, 2]

after step 3
left: [5], right: [4, 6, 7], out: [1, 2, 3]

after step 4
left: [5], right: [6, 7], out: [1, 2, 3, 4]

after step 5
left: [], right: [6, 7], out: [1, 2, 3, 4, 5]

after step 6
left: [], right: [7], out: [1, 2, 3, 4, 5, 6]

at the end
left: [], right: [], out: [1, 2, 3, 4, 5, 6, 7]

したがって、(1) と (4) を理解していると仮定すると、マージソートの別の考え方は次のようになります。他の誰かが書いたものを想像してみてmergesort()ください。あなたはそれがうまくいくと確信しています。次に、その実装を使用して次のmergesort()ように記述できます。

sort(myArray)
{
    leftHalf = myArray.subArray(0, myArray.Length/2);
    rightHalf = myArray.subArray(myArray.Length/2 + 1, myArray.Length - 1);

    sortedLeftHalf = mergesort(leftHalf);
    sortedRightHalf = mergesort(rightHalf);

    sortedArray = merge(sortedLeftHalf, sortedRightHalf);
}

sort再帰を使用しないことに注意してください。「両方の半分を並べ替えてからマージする」とだけ書かれています。上記のマージの例を理解していれば、このsort関数が言うことを実行しているように見えることが直感的にわかると思います...ソート.

さて、もっと注意深く見ると...sort()かなりそっくりですmergesort()！それはそうだからですmergesort()（ただし、再帰的ではないため、基本ケースがありません！）。

しかし、それが私が再帰関数について考えるのが好きな方法です。関数は、呼び出したときに機能すると仮定します。必要なことを行うブラックボックスとして扱います。その仮定を立てると、そのブラック ボックスを埋める方法を理解するのは多くの場合簡単になります。与えられた入力をより小さな入力に分割して、ブラック ボックスにフィードできますか? それを解決した後、残っているのは、関数の開始時に基本ケースを処理することだけです (これは、再帰呼び出しを行う必要がない場合です。たとえばmergesort([])、空の配列を返すだけです。そうではありません)。への再帰呼び出しを行うmergesort())。

最後に、これは少し抽象的ですが、再帰を理解する良い方法は、実際に帰納法を使って数学的証明を書くことです。帰納法による証明を書くのに使われるのと同じ戦略が再帰関数を書くのに使われます:

数学の証明:

  • 基本ケースに対して主張が真であることを示す
  • 一部より小さい入力については真であると仮定します。n
  • その仮定を使用して、サイズの入力に対してまだ真であることを示しますn

再帰関数:

  • 基本ケースを処理する
  • 再帰関数がいくつかのより小さい入力で機能すると仮定しますn
  • その仮定を使用して、サイズの入力を処理しますn
于 2013-09-29T00:15:35.227 に答える
4

は、条件が失敗するmergesort()まで、配列を単純に 2 つに分割します。2 回呼び出しているため、 1 つはtoで、2 番目はtoで、これによりサブ配列がさらに分割されます。iflow < highmergesort()lowpivotpivot+1high

例を見てみましょう：

a[] = {9,7,2,5,6,3,4}
pivot = 0+6/2 (which will be 3)
=> first mergesort will recurse with array {9,7,2} : Left Array
=> second will pass the array {5,6,3,4} : Right Array

left配列と同様に、それぞれに1つの要素が含まれるまで繰り返されますright。最終的には、次のようなものになります。

L : {9} {7} {2} R : {5} {6} {3} {4} (each L and R will have further sub L and R)
=> which on call to merge will become

L(L{7,9} R{2}) : R(L{5,6} R{3,4})
As you can see that each sub array are getting sorted in the merge function.

=> on next call to merge the next L and R sub arrays will get in order
L{2,7,9} : R{3,4,5,6}

Now both L and R sub array are sorted within
On last call to merge they'll be merged in order

Final Array would be sorted => {2,3,4,5,6,7,9}

@roliu による回答のマージ手順を参照してください

于 2013-09-29T15:52:03.260 に答える