エクセルVBAでマージソートと再帰処理(再帰呼出し)...も難しいなあ
マージソートMergeSort
マージソート - Wikipediaうーん、わからん
https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88
マージソート | アルゴリズムとデータ構造 | Aizu Online Judgeここの図解がわかりやすい
http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_5_B
Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第7章 マージソートここも具体的な流れってところが分かりやすかった
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/sort/007.html
Mergeの意味は混合、結合、併合らしいけどマージソートの場合は統合が近いかなあって気がする
マージソートはマージするところが本体なんだけど、その前に分割する作業がある、マージなのに分割!限界まで分割
{4,2,3,1}っていう4つの要素を要素数1個になるまで分割する場合
{4,2}と{3,1}に分割、さらにそれぞれを分割して
{4}{2}{3}{1}ここまで分割する
これをVBAで書いたのがtestDivide↓
↑を例えば配列{4,2,3,1}を渡すマクロ↓を実行すると
Sub test2()
v = Array(4, 2, 3, 1)
Call testDivide(v)
End Sub
1回目の分割が終わって配列1(v1)と配列2(v2)を作成したところで一時停止
{4,2}と{3,1}に分割されている、赤色四角
これで配列1の{4,2}が分割されて{4}と{2}になるはず
一時停止を解除して続行してから、次も同じところで一時停止
OK、{4}と{2}に分割されている(赤色四角)
処理続行して
If UBound(v1) > 0 Then v1 = testDivide(v1)
If UBound(v2) > 0 Then v2 = testDivide(v2)
今回ここは配列1も配列2も要素数1個より大きくないのでスルーになる
次の行は
End Function
になっているから、えー、ここで終わっちゃうの?最初の分割のときの配列2の{3,1}はどうなるの?分割しないの?って思ったら、続けると
配列1は要素数1より大きくないのでスルー
配列2も同様なのでスルー
終わっちゃうよ
え、戻った?
変数の中を見ると
- {4,2,3,1} 元の配列
- {4,2}、{3,1} 最初の分割
- {4,2} 配列1
- {4}、{2} 分割の分割(配列1)
- {3,1} 配列2
- {3}、{1} 分割の分割(配列2)
流れだと1.→2.→3.→4.→2.→5.→6.って感じかなあ
2番のときの{3,1}が終わっていないのを憶えていて自動で巻き戻る
次はどこから処理すればいいのか憶えている感じ
再帰処理スゴイ
スゴイだけに直感的じゃない感じでまだよくわかっていないのよね
分割するときのそれぞれの要素数決定
d1 = WorksheetFunction.Quotient(vAll, 2) '配列1の要素数
Quotientは割り算の商の部分を返してくれるワークシート関数
d1 = WorksheetFunction.Quotient(7, 2)
この場合d1には3が入る、7/2=3.5の商の3
だったら最初から症の部分を返す¥を使って7¥2でいいじゃんって今思った
要素数が奇数のときは右側(配列2)を大きくするようにした
普通の配列は0からだけどセルから直接取り込んだ配列の添字は1から始まるので
何番から始まっていても対応できるようにtestDivideを書き換えると
Function testDivide2(v As Variant) As Variant
'配列を半分に分割、要素数1になるまで分割
'要素数が奇数のときは、3なら1:2に分ける、7だったら3:4
Dim i As Long
Dim lb As Long: lb = LBound(v)
Dim vAll As Long '元の配列の要素数
vAll = UBound(v) - lb + 1
Dim d1 As Long, d2 As Long '配列1と配列2の要素数用
d1 = WorksheetFunction.Quotient(vAll, 2) '配列1の要素数
d2 = vAll - d1 '配列2の要素数
'分割配列作成
Dim v1 As Variant, v2 As Variant
ReDim v1(d1 - 1)
ReDim v2(d2 - 1)
For i = 0 To d1 - 1
v1(i) = v(i + lb)
Next
For i = 0 To d2 - 1
v2(i) = v(i + lb + d1)
Next
'要素数が1になるまで分割
If UBound(v1) > 0 Then v1 = testDivide2(v1)
If UBound(v2) > 0 Then v2 = testDivide2(v2)
End Function
これで分割はできるようになったので次はマージ部分
整列しながらマージしていく
2つの配列を1つにマージしていく
マージ用の配列を作成しておいてそこに
小さい順に入れていく
マージしたもの同士を更にマージしていくと最後には完成する
比較する場所
比較して残った方は何回も比較することになる
この場合は3が何回も比較されていて
3がなくならない限り次の5は比較されない
比較対象がなくなったとき
どちらかの配列の要素がなくなったら残った方の配列の要素を
そのままの順番で入れればマージ完了になる
このマージ部分をVBAで書いたのがMergeMerge1
↓
前半のDo~Loop While部分が比較してマージ用配列に順番に入れているところで
Loopの終了条件が
Loop While c1 <= UBound(v1) And c2 <= UBound(v2)
これで
入れた数をv1とv2それぞれでカウントしていって、どちらかが配列の要素数になったらループ抜け
後半は残った方をマージ用配列に順番に入れているだけ
これでマージ部分もできたので、さっきの分割部分とこれを合わせればマージソート完成する
マージ部分を書いたMergeMerge1これはそのままで
要素数が1になるまで分割して、それからMergeMerge1を呼び出している
'マージする
Dim vv As Variant
vv = MergeMerge1(v1, v2)
最初に渡された配列の添字が0以外から始まっていたときはズレているので、修正しているのが
'マージした配列を元の配列に上書きして返す
For i = 0 To UBound(vv)
v(i + min) = vv(i)
Next
処理時間計測はいつもと同じこれで1万件をソート
Sub sortTestBubble2()
Dim c As Long: c = 10000
Dim v() As Variant
ReDim v(c - 1)
Randomize
For i = 0 To c - 1
v(i) = CLng(c * Rnd)
Next
Dim st As Single
st = Timer
v = MergeSort2(v)
MsgBox Timer - st & "秒"
End Sub
結果
こちらを見るとシェーカーソートよりマージソートのほうが速い
なので僕の書き方が良くないっぽいけど、これ以上は思いつかないなあ
それでもかなり速いことには違いないので100万件でも計測
うーん
前回のコムソートとシェルソートと比較
今までのまとめ
グラフにしてみると
マージソートも速いのがわかる
VBA マージソートの実装と図解 - t-hom’s diaryここを参考にしてMergeMerge1の後半部分を書き直した
http://thom.hateblo.jp/entry/2016/03/21/120449
IfとFor~NextだったのをDo~Loopに変えた
これで100万件ソート
27秒から26秒、少し速くなった
さらに
比較した結果同じ値だったときの処理を削除して速くした
これだと安定ソートじゃなくなるのかも?
結果
25秒
ここまでだなあ
ここ!
コードをコピペして同じように計測したら
16秒!スゴイ
同じマージソートでも僕が書くと25秒だったのが、上手な人が書くと16秒!これだけの差がでる、面白いねえ
関連記事
続きは2日後
エクセルVBAでバブルソート ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
http://blogs.yahoo.co.jp/gogowaten/14787146.html
エクセルVBAで挿入ソート ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
http://blogs.yahoo.co.jp/gogowaten/14799218.html
ソートアルゴリズムまとめ
エクセルVBAで、ソートアルゴリズムとデータの違いによるソート処理時間比較 ( ソフトウェア ) - 午後わてんのブログ - Yahoo!ブログ
https://blogs.yahoo.co.jp/gogowaten/14836198.html