読者です 読者をやめる 読者になる 読者になる

大学院生(情報科学)のブログ

モチベーション維持のためのブログです。

分割統治法とマージソート

以前紹介した挿入ソートは逐次添加法を用いている.

部分配列{A[0\cdots j-1]}をソートした後、1つの要素{A[j]}を正しい場所に挿入する事によってソートされた{A[0\cdots j]}を得た.

多くの結うようなアルゴリズムの構造は再帰であり、その多くの場合、分割統治法に基づいて設計されている.

分割統治法では、問題を元の問題と類似してはいるがサイズが小さいいいくつかの部分問題に分割し、これらの部分問題を再帰的に解いた後、その回を組み合わせて元の問題に対する解を構成する.

以下に3つの段階から構成される再帰の各レベルを示す.

分割 : 問題をいくつかの同じ問題のより小さいインスタンスである部分問題に分割
統治 : 部分問題を再帰的に解く事によって統治する.(部分問題のサイズが十分小さい場合は直接的な方法で解く)
結合 : 部分問題の解を組み合わせて元の問題の解を得る
ここで、分割統治法に従って構成されているマージソートについて紹介する.

マージソートの各段階を以下に示す.

分割 : ソートすべき長さ{n}の列を2つの{\frac{n}{2}}に分割
統治 : マージソートを用いて2つの部分列を再帰的にソート
結合 : 2つのソートされた部分列をマージしてソートされた解を作る
再帰が底をつくのはソートすべき列の長さが1になったときであり、長さ1の配列はソート済みなので何もしない.

マージソートは補助関数の{merge(A,p,q,r)}を用いてソート済みの列を結合する.
{A}は配列、{p,q,r}は添字であり、{p \leq q < r}を満たす.
部分列{A[p\cdots q-1]}{A[q\cdots r]}が共にソート済みであると仮定し、これらを結合する事で単一のソート済み配列{A[p\cdots r]}を得る.

また、番兵と呼ばれる特別な値を持たせる事でプログラムを簡単にしている.この番兵を底に置く事で、判定条件を省略している.今回は番兵に{\infty}を持たせている.

6,8行目の[tex;{for}]文では{A[p \cdots q]}を左部分列に、{A[q+1 \cdots r]}を右部分列に格納している.
10,11行目は左右の部分列の末尾に番兵を格納している.
14行目の{for}文では左右の先頭の要素の内小さい方を{A}に挿入している.
14行目のループの各繰り返しは不変式を維持している.(正当性の証明は省略するが初期条件、ループ内条件、終了条件を確かめる)

この{merge}を用いて{merge\_ sort(A,p,r)}を構築する.
{A[p \cdots r]}に格納された要素をソートする.{p \geq r}のとき、部分列は要素を一つしか含まないのでソート済みである.
それ以外のときは{A[p \cdots r-1]}再帰的に分割する.

f:id:fooloveup:20170315193530p:plain

実行結果
{
A = [5,2,4,7,1,3,2,6] \\
print\; merge\_ sort(A,0,7) \\
[1, 2, 2, 3, 4, 5, 6, 7]}