前回の記事で、私たちは（主に歴史的な興味を引き起こす） 残存マージソートについて知りました 。 今日の傾向は？



合併による順序付けの概念に慣れるために、通常、バランスの取れたマージアルゴリズムが使用されます。 「バランス」という用語は、アルゴリズムが配列とそのサブ配列をほぼ等しい部分に再帰的に分割することを意味します。 今日は、実際にどのように見えるかを見ていきます。



一対の機能は両方の方法で同じです。 とにかく、その「上下」、「上下」はほぼ同じアルゴリズムで、異なる角度から見ただけです。



実際、セグメントの2つの半分を1つのサブアレイにマージする必要があります。 半分は同時に1つの配列にソートされ、両方の反復の現在の要素が比較され、小さい要素は2番目の配列に入ります。

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

セグメントをあるアレイから別のアレイにコピーする。 両方の実装は2つのアレイで動作し、データはメインから補助へ、またはその逆に常に駆動される必要があります。

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

バランスの取れた合併

最初に、配列全体が取得され、その後再帰的降下が開始されます。 配列は、1つの要素のサブ配列に到達するまで二分されます（サブ配列はそれ自体でソートされます）。 その後、再帰は逆の上昇を開始し、途中でサブアレイをマージします（各レベルでサイズが2倍になります）。

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

バランスの取れた上向きの合併

ここでは、最初に（1つの要素から）隣接する最小配列を取得し、それらをペアでマージする方法に沿って、配列の繰り返しが発生します。 各ステップでソートされたサブアレイを2倍にして、隣接ノードを再度マージし、出力で既にソートされたアレイ全体を取得するまで続行します。

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般に、2つの配列をより効率的に使用し、「メイン/補助」の役割を絶えず変更するだけなので、トップダウン実装が望ましいです。 アップストリームバージョンでは、アレイAは常にプライマリであり、アレイBは常に補助です。 その結果、各反復の後、Bからのデータは完全にAに返される必要がありますが、アルゴリズムの複雑さは改善されません。 一方、アセンダントの実装はより単純であり、再帰すらありません。

不均衡な合併

「バランス」という言葉自体から、ある種の信頼性、安定性が吹き飛ばされます。 優れたアルゴリズムのバランスをとる必要があるという印象さえ得られるかもしれません。 そして、「不均衡」は、ある種の揺れと歪みに関連しています。 まあ、本当に、 バランスのとれたものは、 アンバランスのものよりもあらゆる点で優れているべきではありませんか？



実際、もっと悪いです。 もちろん、サブ配列を均等に半分に分割することは（マージソートのバランスで示されるように）実装がはるかに簡単です。 配列を半分に分割し、各半分に再帰を適用します。 実際、この容易さは、バランスの取れていない合併よりもバランスの取れた合併の主な利点です。



以下の出版物では、不均衡な方法を検討します。 それらを理解し、実装するのは著しく困難です。 後続のマージのためのデータは、補助配列全体に均等に均等に分散されるのではなく、多くの一般化されたフィボナッチ数に従います。 そしてこれにより、単純化されたバランスの取れた方法では達成できない強力な結果を達成することができます。

参照資料

マージ （ Google-translate ）、 マージ

シリーズ記事：

• ExcelアプリケーションAlgoLab.xlsm
• 交換ソート
• 挿入ソート
• 選択で並べ替え
• ソートのマージ
  
  
  • トップダウンとボトムアップのバランスの取れた合併
  • マルチフェーズマージソート
  • カスケードマージソート
  • 振動マージソート
  • スレッド化された非混合ソート
  • ソート比較のマージ
• 分布で並べ替え

次のマージソートは、AlgoLabアプリケーションで使用できるようになりました（このExcelアプリケーションを使用してアルゴリズムを学習している人は、ファイルを更新してください）。



配列は一時的に制限されます-そのサイズは2のべき乗でなければなりません（視覚化のプログラミング時に遭遇するいくつかの困難のため）。 少し後に、任意の配列をソートできるようになります。

この記事は、クラウドサービスを使用して組み込みソフトウェアを作成 し、JAVAでモバイルアプリケーションを開発する EDISON Softwareの支援を受けて作成され ました 。