マージソートの考え方や実際のプログラムまで、理解しやすく、忘れないようにまとめたいと思います。
マージソートの擬似言語で書かれたアルゴリズム
マージソートで擬似言語で書くと以下のようなコードになります。
ALDS1_5_Bを参照しています。
/**
A:ソート対象の配列
left:配列の左端のindex,
mid:配列の中間index
right:配列の右端index
*/
merge(A, left, mid, right)
n1 = mid - left;
n2 = right - mid;
// 2つの配列を作成する
create array L[0...n1], R[0...n2]
// 左側
for i = 0 to n1-1
L[i] = A[left + i]
// 右側
for i = 0 to n2-1
R[i] = A[mid + i]
// 番兵を入れる
L[n1] = SENTINEL
R[n2] = SENTINEL
i = 0;
j = 0;
// 2つの部分配列をマージする①
for k = left to right-1
if L[i] <= R[j]
then A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
Merge-Sort(A, left, right){
if left+1 < right
then mid = (left + right)/2;
call Merge-Sort(A, left, mid)
call Merge-Sort(A, mid, right)
call Merge(A, left, mid, right)
マージソートのアルゴリズム
この擬似言語のアルゴリズムからマージソートは以下の手順で実行されます。
1.指定されたn個の要素を含む部分配列を
それぞれn / 2の要素を含む2つの部分配列に分割する(divide)
2.分割した2つの部分配列をマージソートでソートする(solve)
3.ソートした2つの部分配列をマージする
マージソートはソート済みの2つの部分配列を結合するときのアルゴリズムが鍵になっています。
擬似言語のアルゴリズムでは、①の箇所が該当します。
2つの配列LとRは昇順にソートされていることを前提とし、
LとRのすべての要素が昇順となるようにソート済みの数列を格納するAにコピーしています。
2つの部分配列は、昇順にソートされていることが前提と書きましたが、
マージソートでは、要素数1からスタートし、部分配列を昇順に結合していくので、
2つの部分配列はソートされていることになります。
部分配列LとRはソート済みであることから、擬似言語でのアルゴリズムのコードからわかるように、
計算量は、O(n1 + n2)となります。
マージソートの結合する箇所を図解する
マージソートの要となる結合部分のアルゴリズムを図示してみます。
マージのアルゴリズムは、以下のコードでした。
// 番兵を入れる
L[n1] = SENTINEL
R[n2] = SENTINEL
i = 0;
j = 0;
// 2つの部分配列をマージする①
for k = left to right-1
if L[i] <= R[j]
then A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
まず、以下の2つの部分配列L・Rと、結合する整列した配列Aがあるとします。
L:1,6
R:2,3,9
A:***
部分配列のL・Rは要素が2つ以上入っているので、
Aには、すでに整列途中の結果が入っていることになります。
擬似言語のアルゴにあるように、それぞれに番兵(最大の数値今回はSとする)を代入します。
L:1,6,S
R:2,3,9,S
1回目の比較
Lのindex0とRのindex0を比較して、小さい方をA[left]に代入します。
L:1,6,S R:2,3,9,S A:1
Lのindex0の値1が挿入されたので、Lのindex対象の変数iを1つ増やします。
2回目の比較
L:1,6,S R:2,3,9,S A:1,2
Rの2代入されます。
Rのindex対象の変数jを1つ増やします。
3回目の比較
L:1,6,S R:2,3,9,S A:1,2,3
Rの3が代入されます。
4回目の比較
L:1,6,S R:2,3,9,S A:1,2,3,6
Lの6が代入されます。
次からLは番兵を指すようになります。
最後の比較
L:1,6,S R:2,3,9,S A:1,2,3,6,9
最後の比較になります。
Lは番兵をさすので、Rの9がAに挿入されます。
forループの比較回数は、left to right - 1とleftとrightの合計の要素数になっているため、
ここで比較が終了します。
番兵と比較する要素数で判断することによって、O(n1 + n2)の処理数を実現しています。
mergeSort関数の解説
結合のアルゴリズムがわかったところで、mergeSort関数部分を図解していきます。
mergeSortの擬似言語での関数は以下です。
Merge-Sort(A, left, right){
if left+1 < right
then mid = (left + right)/2;
call Merge-Sort(A, left, mid)
call Merge-Sort(A, mid, right)
call Merge(A, left, mid, right)
引数Aには、対象となるソートしたい配列を、
leftには、部分配列の先頭を、rightには、末尾+1のindexを指定します。
left + 1 < right
により、要素が1以下の場合は処理しないようにしています。
mid = (left + right)/2;
Merge-Sort(A, left, mid)
Merge-Sort(A, mid, right)
探索する範囲を狭めて、再帰処理を行なっています。
最終的には、Merge-Sortに渡す対象のindexが2つの部分配列の要素数がそれぞれ
1になるようにすることで、昇順に整列する箇所が機能するようにしています。
mergeSortの工程を図解する
では最後にmergeSortの工程を図解します。
数列859263714をマージソートにかけています。
黒矢印が分割する工程を、赤矢印がマージする工程を示しています。
mergeSortの計算量を考える
merge関数の処理の計算量は前述したように0(n1 + n2)になります。
上図にあるように、9個の数を1個になるまで、分割しようとすると、
9 → 5 → 3 → 2 → 1
の4回の分割が必要になり、階層は5になります。
このことから、階層は一般に
$log_{2}n$個になります。
階層階ごとに行われる全てのマージの総計算量はO(n)になるので、
マージソートの計算量はO(nlogn)になります。
0 件のコメント:
コメントを投稿