20230102基本情報技術者試験的な備忘録（マージソートをVBAで考える・再帰処理）
パソコン素人です。
基本情報技術者試験の問題・テキスト等を見て気になったメモです。
間違っているので詳しく見ないで下さい。すみません。
（引用した内容等、その他問題があれば削除いたします。）
基本情報技術者試験の出題範囲「アルゴリズムとデータ構造」で、「マージソート」がある。
（マージソートの説明は省略します。）
ネットには、pythonで「マージソートを実装」というのが結構出ている。
ネット上の「paiza.io」で入れてみると確かに結果が出るが、「paiza.io」でのpythonのステップ実行ができない。
（自分が知らないだけかもしれないが。）
で、ステップ実行やブレークポイントの設定がしやすいVBA（エクセル）でやってみた。
参考にしたpythonのコードは、
@Yu-ya-Shimizu様の「Pythonで学ぶアルゴリズム 第20弾：並べ替え（マージソート）」
です。感謝。
これ以外にもPythonでは方法はいくつかある。
実際にはマージソートは配列を分解（分割）しないでするプログラムが多いが、
これは実際に配列を分割して、新たに配列に並べ替えて統合していたので、これを見本にしました。
で、作り始めると、再帰処理が必須らしい。
（再帰処理の説明も省略します。）
VBAでは配列がpythonのようにはシンプルにできない。
要素数を定義したり・・・（前回のVBAの配列備忘録参照）。
途中、ブレークポイントやローカルウィンドウで変数の推移や再帰の流れを確認していったがよく分からない。
で、どうしようかとネットを再度見ると、VBAで作成した方がいた。
「もしも普通のサラリーマンがお金とITを学んだら」さんのマージソート。
（感謝）
詳しく解説してくれ、完成品を表示していた。
（最初からこれで良かったのかも・・・）
で、それを参考に作成したのが下記。
（「もしも普通のサラリーマンがお金とITを学んだら」さんとは少し違ってます。）
************************************コード（間違ってたらすみません）
Option Explicit
Sub macro1_mergesort_saiki_hairetu() 'hairetuが並び変わってhairetu_goが入るように
Dim hairetu As Variant
Dim hairetu_go As Variant
ReDim hairetu(3) '0番使う（これなら4個使える）
hairetu(0) = 5
hairetu(1) = 3
hairetu(2) = 4
hairetu(3) = 1
ReDim Preserve hairetu(7) '0使う（これなら8個使える）
hairetu(4) = 2
hairetu(5) = 10
hairetu(6) = 9
hairetu(7) = 8
ReDim Preserve hairetu(8) '0使う（これなら9個使える）
hairetu(8) = 6
hairetu_go = bunkatu(hairetu) '戻ってくる配列
Stop 'ローカルウィンドウで確認して下さい。（いろんな箇所でstopやステップインF8を使うと流れが分かります。）
End Sub
Function bunkatu(ByRef hairetu As Variant) As Variant '１マージソート前の分割処理
Dim buf As Variant
buf = hairetu 'そのまま配列を受ける
If UBound(buf) + 1 <= 1 Then '再帰処理の終了条件
bunkatu = buf
Else '分割処理
Dim mid As Long
mid = (UBound(buf) + 1) / 2 '半分に分割するため
'追記疑問
'VBAの配列は、pythonのようなリストの切り出し[:mid]とかできないのかもしれない。
Dim left_hairetu As Variant 'integerだと要素数設定必要（ないとエラー）
'データを分割・格納
Dim a As Long
ReDim left_hairetu(mid - 1) '０まで使えるので-1
For a = 0 To mid - 1 '前半（left）を回す
left_hairetu(a) = buf(a)
Next a
Dim right_hairetu As Variant
Dim b As Long
ReDim right_hairetu(UBound(buf) - mid) '配列（使える数）なので＋１はしない
Dim c As Long
For b = mid To UBound(buf) '後半(right)を回す＋１はしない
right_hairetu(c) = buf(b) '配列0から入れる
c = c + 1
Next b
'再帰
Dim left_saiki As Variant
left_saiki = bunkatu(left_hairetu)
'再帰
Dim right_saiki As Variant
right_saiki = bunkatu(right_hairetu)
'統合（再帰後配列出し）
Dim mergego_hairetu As Variant
mergego_hairetu = Merge(left_saiki, right_saiki)
'結果（マージ後配列戻し）
bunkatu = mergego_hairetu
End If
' Stop
End Function
Function Merge(left_saiki, right_saiki) '２比較して入れ替えて配列を統合
ReDim result(UBound(left_saiki) + 1 + UBound(right_saiki) + 1 - 1) 'Uboundが0なら+1する。（足しても０だから）。
Dim i As Long, j As Long
Dim cnt As Long
Do While (i <= UBound(left_saiki)) And (j <= UBound(right_saiki))
If left_saiki(i) <= right_saiki(j) Then '左<=右のとき(左小さい)
'左から取り出してresultに追加（入れる）
result(cnt) = left_saiki(i)
i = i + 1
Else '右小さい
result(cnt) = right_saiki(j) '右から取り出してresultに追加（入れる）
j = j + 1
End If
cnt = cnt + 1 '(出る時にカウント)
Loop
'左右差（端数のこり処理（左右上記処理でどうしても発生）) 残りは複数の場合あり・・・
Dim d As Long
If i < UBound(left_saiki) + 1 Then '右辺大きいなら残りがある
For d = i To UBound(left_saiki)
ReDim Preserve result(cnt)
result(cnt) = left_saiki(d)
cnt = cnt + 1
Next d
End If
If j < UBound(right_saiki) + 1 Then
For d = j To UBound(right_saiki)
ReDim Preserve result(cnt)
result(cnt) = right_saiki(d)
cnt = cnt + 1
Next d
End If
Merge = result 'function bunkatuに返す
End Function
********************************************
これで、ローカルウィンドウなどで再帰処理を見ていく。
単純に、再帰は、ループから出る処理（if文など終了条件）を付けておく。
（無限ループしないように。）
また、再帰は上→下へ進むだけでなく、再帰するとそれより下へ行かず、
再帰を繰り返し、終了地点（上記のif文など）まで来ると、巻き戻るように逆順で動く。
今回の場合、functionが２つあり、bunkatuで再帰をし、mergeの方で並び替えて要素を結合するが、
bunkatuを全部やり終えた時点では、途中の分解した要素がたくさんできて、
mergeで途中分解したものを逆順で結合していくような感じだった。
再帰で順を追うのはなかなか大変だと感じました。
