mergesortの再帰を理解する

私が見ているmergesortの実装のほとんどはこれに似ています。アルゴリズムの紹介、私が検索するオンラインのインパクトと一緒に。私の再帰チョップは、フィボナッチ世代（それは十分に単純だった）を乱すよりもそれほど進んでいないので、多分、私の心を吹き飛ばしている複数の再帰ですが、コードを踏んでも、私がヒットする前に何が起こっているのか理解できませんマージ関数。mergesortの再帰を理解する

どのようにこれを実行していますか？ここでのプロセスをより深く理解するためには、何か戦略や読書がありますか？

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]; 
}

出典

2013-09-28 2c2c

によって与えられた答えでマージする手順を参照してください：あなたはこれに似た何かがあるでしょう最後にそれは本当に「分割」と呼ばれるべきです。

ここでは、処理中のアルゴリズムの視覚化があります。

enter image description here

関数は再帰たびに、それはそれの左半分から始まる、入力配列のますます小さく細分化に取り組んでいます。関数が再帰から復帰するたびに、関数は継続され、右半分で作業を開始するか、再度再帰して大きな半分で作業します。マージソートの再帰部分については、この

[************************]mergesort 
[************]mergesort(lo,mid) 
[******]mergesort(lo,mid) 
[***]mergesort(lo,mid) 
[**]mergesort(lo,mid) 
[**]mergesort(mid+1,hi) 
[***]merge 
    [***]mergesort(mid+1,hi) 
    [**]mergesort*(lo,mid) 
    [**]mergesort(mid+1,hi) 
    [***]merge 
[******]merge 
     [******]mergesort(mid+1,hi) 
     [***]mergesort(lo,mid) 
     [**]mergesort(lo,mid) 
     [**]mergesort(mid+1,hi) 
     [***]merge 
     [***]mergesort(mid+1,hi) 
     [**]mergesort(lo,mid) 
      [**]mergesort(mid+1,hi) 
     [***]merge 
     [******]merge 
[************]merge 
      [************]mergesort(mid+1,hi) 
      [******]mergesort(lo,mid) 
      [***]mergesort(lo,mid) 
      [**]mergesort(lo,mid) 
      [**]mergesort(mid+1,hi) 
      [***]merge 
       [***]mergesort(mid+1,hi) 
       [**]mergesort(lo,mid) 
       [**]mergesort(mid+1,hi) 
       [***]merge 
      [******]merge 
        [******]mergesort(mid+1,hi) 
        [***]mergesort(lo,mid) 
        [**]mergesort*(lo,mid) 
        [**]mergesort(mid+1,hi) 
        [***]merge 
        [***]mergesort(mid+1,hi)  
        [**]mergesort(lo,mid) 
         [**]mergesort(mid+1,hi) 
        [***]merge 
        [******]merge 
      [************]merge 
[************************]merge

出典

2014-03-18 23:42:19 slashdottir

行うには明白なことは、小さなアレイ上で、このマージソートをしようとするだろう紙の上に、サイズ8（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は、再帰を使用していないことを

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()はちょうどmergesort()のようになります！それはmergesort()です（再帰的ではないため、基本ケースはありません）。

しかし、これは私が再帰関数を考えるのが好きです。関数を呼び出すと関数が動作すると仮定します。あなたが必要とするものをブラックボックスとして扱います。あなたがその前提を作るとき、そのブラックボックスを記入する方法を考えることは、しばしば簡単です。与えられた入力に対して、それを小さな入力に分割してブラックボックスに供給できますか？あなたがそれを解決した後で残っている唯一のことは、関数の開始時にベースケースを処理することです（再帰呼び出しを行う必要がないケースです）。たとえば、mergesort([])は空の配列を返します。 mergesort()への再帰呼び出しを行いません）。

最後に、これは少し抽象ですが、再帰を理解する良い方法は、実際に誘導を使用して数学的証明を書くことです。誘導により証明を書き込むために使用したのと同じ戦略は、再帰関数を記述するために使用される：

数学証明：

基地ケース
はそれが小さい入力に対して真であると仮定するための請求項が真であることを示しますいくつかのn
よりも、それはサイズの入力のためにまだ本当であることを示すために、その仮定を使用しn

再帰関数：

ベースケースを扱うには、あなたの再帰関数は、いくつかのn
mergesort()は単純に配列を分割n

出典

2013-09-29 00:15:35 rliu

サイズの入力を処理するためにその仮定を使用して、より少ない入力で動作することを想定しますifの条件が満たされなくなるまで、2つの半分になります。これはlow < highです。 mergesort()を2回呼び出すと、1つはlowからpivotに、もう1つはpivot+1からhighになります。これにより、サブアレイがさらに分割されます。あなたは、各leftで1つの要素だけでなく、right配列を持つまで

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

それが繰り返されます：

に例を取ることができます。

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-29 15:52:03

同様

は、私はこのpageは非常に非常に有用であることがわかってきました。実行中のコードに従うことができます。最初に実行されるものと次に続くものを示します。

トム

出典

2015-04-11 13:02:12

マージソート：

1）半
2のアレイを分割）ソート左半分
3）ソート右半分
4）は、2つの半体をマージ一緒に

出典

2015-12-11 20:25:58 abe312

このように回答された場合は謝罪します。私はこれが深い説明ではなく単なるスケッチであることを認めています。

実際のコードがどのように再帰にマップされているのか分かりませんが、私はこのように一般的な意味で再帰を理解することができました。

例として、ソートされていないセット{2,9,7,5}を入力します。 Merge_sortアルゴリズムは、以下の簡潔さのために「ms」で示されている。

ステップ1：MS（MS（MS（2）、MS（9））、MS（MS（7）、MS（5）））

ステップ我々はとしての動作をスケッチすることができ2：MS（MS（{2}、{9}）、MS（{7}、{5}））

ステップ3：MS（{2,9}、{5,7}）

ステップ4：{2,5,7,9}

を（{2}ような）一重のmerge_sortに注意することが重要であるに過ぎませんシングレット（ms（2）= {2}）、再帰の最も深いレベルで最初の答えが得られるようにします。残りの答えは、内部再帰が終了して一緒にマージされるので、ドミノのように転がります。

アルゴリズムの天才の一部は、ステップ1の再帰式を自動的に構築する方法です。何が私を助けたのは、上記のステップ1を静的な式から一般的な再帰に変える方法を考える運動でした。

出典

2015-12-28 23:12:50

process to divide the problem into subproblems 例は、再帰の理解に役立ちます。 int A [] = {短絡される要素の数}、int p = 0; （恋人インデックス）。 int r = A.length - 1;（高いインデックス）。

class DivideConqure1 { 
void devide(int A[], int p, int r) { 
    if (p < r) { 
     int q = (p + r)/2; // divide problem into sub problems. 
     devide(A, p, q); //divide left problem into sub problems 
     devide(A, q + 1, r); //divide right problem into sub problems 
     merger(A, p, q, r); //merger the sub problem 
    } 
} 

void merger(int A[], int p, int q, int r) { 
    int L[] = new int[q - p + 1]; 
    int R[] = new int[r - q + 0]; 

    int a1 = 0; 
    int b1 = 0; 
    for (int i = p; i <= q; i++) { //store left sub problem in Left temp 
     L[a1] = A[i]; 
     a1++; 
    } 
    for (int i = q + 1; i <= r; i++) { //store left sub problem in right temp 
     R[b1] = A[i]; 
     b1++; 
    } 
    int a = 0; 
    int b = 0; 
    int c = 0; 
    for (int i = p; i < r; i++) { 
     if (a < L.length && b < R.length) { 
      c = i + 1; 
      if (L[a] <= R[b]) { //compare left element<= right element 
       A[i] = L[a]; 
       a++; 
      } else { 
       A[i] = R[b]; 
       b++; 
      } 
     } 
    } 
    if (a < L.length) 
     for (int i = a; i < L.length; i++) { 
      A[c] = L[i]; //store remaining element in Left temp into main problem 
      c++; 
     } 
    if (b < R.length) 
     for (int i = b; i < R.length; i++) { 
      A[c] = R[i]; //store remaining element in right temp into main problem 
      c++; 
     } 
}

出典

2017-08-15 05:06:21

答えに説明を追加してください。@Shravan Kumar –

コードを答えとしてダンプするのを避けてください。関連するコーディング経験を持っていない人にとっては、あなたのコードは明らかではないかもしれません。 [解明、文脈を含めるようにあなたの答えを編集して、あなたの答えに何らかの制限、前提条件、簡素化について言及してください。]（https://stackoverflow.com/help/how-to-answer） –

これは古い質問ですが、私がマージソートを理解するのを助けたものの私の考えを投げたいと思っていました。

二つの大きな部分が（征服）と共にアレイをマージ小さいチャンク（分割）

への配列のソート

分割をマージあり

recurisonの役割単に分割部分である。

は、私が何をほとんどの人が混乱すると、彼らは分割でのロジックと分割するかを決定がたくさんあると思いますが、ソートの実際のロジックのほとんどはマージに起こることだと思います。再帰は単純に分割して前半を行い、後半は本当にループしています。

は、私が（「ピボット」を選択に大きく依存している）私はクイックソートとマージソートを混同する簡単な方法だからマージソートと単語「ピボット」を関連付けない推薦するピボットを言及したがいくつかの回答を参照してください。それらは両方とも「分割と征服」アルゴリズムです。マージソートの場合、分割は常に中央で行われますが、クイックソートの場合は、最適なピボットを選択するときに分割で巧みになることができます。

出典

2017-12-02 20:15:23 aug

再帰メソッドを呼び出すと、実際の関数がスタックメモリにスタックされると同時に実行されません。条件が満たされないときは、次の行に行くでしょう。

が

int a[] = {10,12,9,13,8,7,11,5};

だからあなたのメソッドのマージソートは、以下のように動作します：：だから

mergeSort(arr a, arr empty, 0 , 7); 
mergeSort(arr a, arr empty, 0, 3); 
mergeSort(arr a, arr empty,2,3); 
mergeSort(arr a, arr empty, 0, 1); 

after this `(low + high)/2 == 0` so it will come out of first calling and going to next: 

    mergeSort(arr a, arr empty, 0+1,1); 

for this also `(low + high)/2 == 0` so it will come out of 2nd calling also and call: 

    merger(arr a, arr empty,0,0,1); 
    merger(arr a, arr empty,0,3,1); 
    . 
    . 
    So on

空ARRのすべてのソート値ストア

が、これはあなたの配列であることを考えてみましょう。再帰関数の働きを理解するのに役立つかもしれない

出典

2018-01-16 06:38:33 Milind

mergesortの再帰を理解する

答えて

関連する問題