この記事では、
自分の理解の範囲内で、
マージインサーションソートをソート初心者に説明することを目標にする。
別名などは特に記載せず、
ロジックを可能な限りわかりやすく説明する記事にしたい。
初めて勉強する人は、
この記事をみておけばだいたい実装イメージが湧くと思う。
マージインサーションソートとは
ひとことでいうと、
元の数列をmain_chainとsub_chainに分け、
適切にmain_chainにsub_chainの要素をマージしていくソート方法
である。
最悪比較回数を最小にするためのソート方法なのだが、
main_chainとsub_chainってなんぞやだと思うので早速次で説明する。
１．main_chainとsub_chainを作る
例えば９個の以下の数列
[500, 350, 400, 250, 0, 50, 100, 200, 150]があるとする。
その時、
- 隣同士とかで適当にペア作る
- ペア内で大小関係を作る
- ペアの大きい方をもとにペアごとソートする。（再帰的に。）
- 下の画像のように、
上側(大きい方の羅列a[50, 200, 400, 500])をmain_chainとしてaとして表し、
下側(小さい方の羅列b[0, 100, 250, 350]）をsub_chainとしてbとして表す。
a0とb0, a1とb1などはペアとしてお互いに対応している。
2: sub_chainの要素bをmain_chainにマージする
いま、
main_chain a[50, 150, 400, 500]
sub_chain b[0, 100, 250, 350]である。
ここで、
sub_chainの要素をmain_chainに入れていくことを考えると、
sub_chainの要素b1(100)は、対応するmain_chainの要素a1(150)以下が確定のため、
a1の左側へ必ず入ることがわかる。
よって、a1(150)より左側への挿入を考えればいい。
例えば、b3=350をaに入れようとすると、
a0~a2の、[50, 150, 400]に対して、
４つの箇所いずれかにb3を挿入することを考える。
このときb0~bnがあるが、
どの順でaに挿入していけば最悪比較回数を最小にできるだろうか？
ちなみに。
これは少し言い換えると、
b0を挿入するのにかかった比較回数＋
b1を挿入するのにかかった比較回数＋…＋
bnを挿入するのにかかった比較回数 を最小にする
つまりbの要素の比較回数の合計を最小にする挿入順に最適化せよ！ってことだ。
少し考えてみてほしい。
これは２つ押さえれば簡単だ。
１つ目
「比較回数とは、二分木の深さのことである」ということ
こんな感じ。
①と②では、木の深さが２なので最悪比較回数は２回。
③からは、木の深さが３に突入してしまうため、最悪比較回数は３回になってしまう。
③よりもあと配列の要素が４こ多かった場合、
更に次の深さにノードが置かれるので、深さは４、最悪比較回数も４になる。
となると、
b0を挿入するのにかかった比較回数＋
b1を挿入するのにかかった比較回数＋…＋
bnを挿入するのにかかった比較回数
を最小にするには、
これらのｂ要素のうち、
できるだけを木の深さ１で比較する。
↓
できるだけを木の深さ２で比較する。
↓
できるだけを木の深さ３で比較する。
↓
。。。
とやっていけば、
比較合計数は最小にできる。
これは「欲張りプラン」と名付ける
２つ目
木の深さは「逆順」で固定できる
b(n) -> b(n-1) ->b(n-2)->…->b(1)->b(0)の順に「逆順」としてmain_chainに挿入を考える。
ここでさっき言った、
b(n)を挿入するとき、
a(n) >= b(n)なので、b(n)はa(n)よりも必ず左側に入ること
(a(0)~a(n-1)を比較対象にすればいいこと)
を思い出しておく。
(i)b(n)の挿入を考えるとき、
比較すべきはa(0)~a(n-1)のn個のノードで比較し挿入位置を決める
(ii)b(n-1)の挿入を考えるとき、
比較すべきはa(0)~a(n-2)のn-1個のノードと、(i)で挿入したb(n)１個、
合計n個のノードで比較し挿入位置を決める。
(iii)(i)(ii)に引き続いて同じ（たまにラッキーなこともあるがそれはさておく）
このように、
a側は逆順でindexがデクリメントしていくので１ずつ減り、
b側は前回挿入したbを挿入するので１ずつ増える。
結果として、
逆順にすることで、比較すべき対象ノードをn個に固定することができる
３：前項の「欲張りプラン」を実行する
前項ででた抑えてほしいポイント２つを使えば欲張りプランは実行できる
もう一度載せるが、
b0を挿入するのにかかった比較回数＋
b1を挿入するのにかかった比較回数＋…＋
bnを挿入するのにかかった比較回数
を最小にするには、
これらのｂ要素のうち、
できるだけを木の深さ１で比較する。
↓
できるだけを木の深さ２で比較する。
↓
できるだけを木の深さ３で比較する。
↓
。。。
とやっていけば、
比較合計数は最小にできる。
１から順に出来るだけのbを、
ノード数を固定しながらいれていけばいい
これを頭に入れればあとはスムーズに理解できる。
bをmain_chainに入れていく順序は以下の順だ。
初期、
main_chain a[50, 150, 400, 500]
sub_chain b[0, 100, 250, 350]である。
- b(0)=0は確定でa(0)=50より左側なので無条件に挿入。
- b(2)->b(1)の順に挿入を考えることで、比較ノードを３に固定できる。
(深さは２の完全2分岐でできるだけｂをいれる) - b(4)->b(3)の順に挿入を考えることで、比較ノードを７に固定できる。
(深さは３の完全2分岐でできるだけｂをいれる) - b(10)->b(9)->… ->b(6) ->b(5)の順で。。。(深さは４の完全２分岐)
とやっていくと、
b(0)->b(2)->b(1)->b(4)->b(3)->b(10)->b(9)->…
この順なら欲張りプランを満たせる。
どうして、２や４や10から逆順していけばいいと思いつくのか。
それは、
欲張りプランの
できるだけを木の深さ１で比較する。
↓
できるだけを木の深さ２で比較する。
↓
できるだけを木の深さ３で比較する。
の部分を満たそうとすると自然に出てくる。
例えば上のステップの３、比較ノードを７に固定したいとき、
ステップ２の完了段階ではa(2)より左側にはb(2), b(1), b(0)がすでに挿入されている。
[b(0), a(0), b(1), b(2), a(1), a(2), a(3), a(4), a(5), …, a(n) ]
ステップ２でindex = ｘ(x+1個のノード)から逆順を始めたとき、
ステップ2の完了時(ステップ3の初期時)、
とあるa(x)の左側にはすでにbが(x + 1)個挿入されています。
a(x)~a(0)の個数とb(x)~b(0)の個数は同じなので
ステップが完了するとa(x)の左側には2 * (x + 1)個ノードがあることになる。
今回だとa(2)含め左側には、上の通り、６個すでにノードがある。
ノードを７に固定したい場合、
１つしかノードを追加できないので、
b(4)の挿入を考え、a(4)より左側、a(3)のみを新たに追加する。
４：この順序は数列として表せるか
b(0)->b(2)->b(1)->b(4)->b(3)->b(10)->b(9)->…
この数列、
０, 2, 4, 10, 20, …それぞれの項で前項の直後までデクリメントしているが、
いったいどんな数列として表せるだろうか。
数列として一般化できたらプログラムに落とし込めるのだが。
そこで、一旦この数列前項に１を足してみる。（おまじない）
1, 3, 5, 11, 21, …
これは、
J(n) = 2 * J(n – 2) + J(n – 1) …★
をみたしているではないか！！
(ちょっとズルすぎる気もするが。)
とにかくこの数列をindex化させるために、
各項で-1を行い、（これがさっきのおまじないの正体か？）
０, 2, 4, 10, 20, …
各項から逆順に前項の直後までデクリメントすることで
b(0)->b(2)->b(1)->b(4)->b(3)->b(10)->b(9)->…
が得られる。
この順にsub_chain要素をmain_chainにマージすることで、
マージインサーションソート(最悪比較回数を最小にするソート)は達成される。
(ちなみに★の数列はJacobsthal numbersという名前で、
CS分野でたまに応用されるらしい)
コメント