Data-structures-algorithms-merge-sort-algorithm

データ構造-ソートアルゴリズムのマージ

マージソートは、分割統治技術に基づくソート技術です。 最悪の場合の時間の複雑さはΟ（n log n）であり、最も尊敬されるアルゴリズムの1つです。

マージソートは、最初に配列を等しい半分に分割してから、ソートされた方法でそれらを結合します。

マージソートの仕組み

マージソートを理解するために、次のようにソートされていない配列を取ります-

Unsorted Array

マージソートでは、アトミック値が達成されない限り、最初に配列全体が均等に半分に分割されることを知っています。 ここでは、8つのアイテムの配列がサイズ4の2つの配列に分割されていることがわかります。

ソート部門の統合

これは、元のアイテムの外観の順序を変更しません。 次に、これら2つの配列を半分に分割します。

ソート部門の統合

これらの配列をさらに分割し、これ以上分割できない原子値を達成します。

ソート部門の統合

今、私たちはそれらが分解されたのとまったく同じ方法でそれらを結合します。 これらのリストに記載されているカラーコードに注意してください。

最初に各リストの要素を比較し、次にそれらをソートされた方法で別のリストに結合します。 14と33がソートされた位置にあることがわかります。 27と10を比較し、2つの値のターゲットリストで最初に10を置き、次に27を置きます。 19と35の順序を変更しますが、42と44は順番に配置されます。

並べ替えの結合を結合

結合フェーズの次の反復では、2つのデータ値のリストを比較し、それらを検出されたデータ値のリストにマージして、すべてをソートされた順序にします。

並べ替えの結合を結合

最終的なマージの後、リストは次のようになります-

ソートのマージ

次に、マージソートのプログラミングの側面を学習します。

アルゴリズム

マージソートは、リストが分割できなくなるまで、リストを均等に分割し続けます。 定義上、リスト内の要素が1つだけの場合は、ソートされます。 次に、マージソートは、小さいリストを結合して、新しいリストもソートしたままにします。

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

疑似コード

マージソート機能の擬似コードが表示されます。 アルゴリズムでは、2つの主要な機能-分割とマージを指摘しています。

マージソートは再帰で機能し、同じ方法で実装を確認します。

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure

Cプログラミング言語でのマージソートの実装については、リンク：/data_structures_algorithms/merge_sort_program_in_c [ここをクリック]をご覧ください。