fc2ブログ



マージソート Merge Sort

2007.02.18 01:06  整列

マージソートは、高速でかつ安定なソートアルゴリズムです。しかも、効率はやや劣りますが、クイックソートと比べると実装が簡単で理解もし易いアルゴリズムです。高速で安定という特徴から、様々なところで実用されています。

マージソートのアルゴリズムは分割統治法を応用します。そして、マージソートは分割統治法を説明するための最も良い例ともなるので、分割統治法のアイデアもついでに知ることができます。下図は、マージソートの流れを表しています。

mergeSort.gif


ステップ1配列による入力データ
ステップ2 配列を2つに分割する
ステップ3 分割された部分配列をさらに分割する
ステップ4 分割された部分配列をさらに分割する
ステップ5 部分配列の要素数が 1 でこれ以上分割することができないので、2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ6 分割された部分配列をさらに分割する
ステップ7 2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ8 2 つの部分配列を統治する。統治するときに要素を昇順にソートする.
ポイント:これら 2 つの部分配列の要素はすでにソート済みである
ステップ9-14 同様に、ステップ 2 で分割された部分配列を分割-統治する
ステップ15 2 つの部分配列を統治する。統治するときに要素を昇順にソートする.
ポイント:これら 2 つの部分配列の要素はすでにソート済みである.
配列のソートが完了する


マージソートの流れの論理的な構造は、ツリー(木)となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。しかし、データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。


マージソートのプログラムは、mergeSort と merge の2つの部分から構成されています。まず、配列全体を指定した mergeSort を呼び出します。mergeSort は与えられた配列を前半後半の2つに分割します。その2つについてそれぞれさらに mergeSort を行います(再帰により実現する)。mergeSort は配列の要素数が 1 以下のときは何もせずに終了します。そして、各 mergeSort の最後で、分割された前後2つの配列を merge します。merge を実行する時点で、mergeSort( 部分配列の前半 ) と mergeSort( 部分配列の後半 ) がすでに終了しているので、merge はすでにソートされている部分配列の前半と後半に対して実行されます。言い換えれば、merge の役割は、すでにソートされている2つの部分配列を1つのソートされた部分配列にすることです。

プログラム例:部分配列の先頭のインデックスを left、部分配列の(末尾 + 1)のインデックスを right とした場合





この merge 関数は番兵を使ってやや巧妙な処理をしています。以下の図は、この merge のメカニズムをカードの操作で表したものです。左右にカードの束があり、各束のカードは小さい順に整列されているものとします。そして、カードの最下部に番兵としてジョーカーを追加配置します。

マージの処理は、各カードの山のてっぺんの値を比べ、小さい方を選択して順番に並べていきます。この操作の過程で、あるカードとジョーカーを比べる局面が発生しますが、ジョーカーが選ばれることはありません。つまり、番兵にはどのカード(数字)と比べても負けることのない大きな数を割り当てるのです。

ジョーカーすなわち番兵の設置によって、マージの際にカードの束が空になったか否かのチェックをする必要がなくなります。なぜなら、カードを選択する回数を、ジョーカーを除いたカードの合計値とすれば、ジョーカーが比べられることも、カードの束が空になることもないからです。束が空になったか否かのチェックは、プログラム上では配列の範囲を超えるか否かのチェックとなるので、番兵の設置は処理の高速化にも繋がり(微々たるものですが、)プログラムが読みやすくなります。

mergeSortMerge.gif


次に示す、merge のプログラムは、さらに巧妙なテクニックを用いています。プログラムの動作を考えてみましょう。



マージソートの計算効率は、データがどのような特徴を持っていても O(nlogn) となります。上図に示したマージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるからです。

実戦でマージソートを自分で最初から実装することはまずないと思われますが、分割統治法、再起、番兵のアイデア、などを学べる良いアルゴリズムの1つではないでしょうか。
スポンサーサイト



| コメント(2) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

すごくわかりやすかったですv-10

ありがとうございましたv-119v-119

eri | URL | 2007.02.22 11:57 | 編集

コメントありがとうございましたv-11
もっとわかり易く書きたいのですが、説明って難しいですi-6

管理者 | URL | 2007.02.25 16:17 | 編集

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ