一言で説明すれば、コムソートって VB6 にすごく適したソートアルゴリズムなんじゃない？ってこと。追記: 訂正記事があるので読んでね。
uBMplay は仕様上読み込んだオブジェをソートする必要があるので、そのためにクイックソートを使っているのだけど、先日デバッグをしていて、いくらなんでも遅すぎることに気がついた。
知っている人も多いと思うが、VB6 は C 言語と違ってクイックソートがデフォルトで用意されていない。そのため自前でコードを書かないといけないのだけど、なんと過去の自分はここで横着をして、ネット上から適当なコードを拾って使っていたのだ。そのコードをよく見てみると、"一般的な" クイックソートの実装から少しずれていることに気がついた (以降、クイックソートもどきと呼ぶ)。そこで "一般的な" クイックソートに書き直してテストしてみたところ、クイックソートもどきとは比較にならないほど速くなった。
・・・ところが、ここで問題が発生。一部を除き、ほとんどの BMS ではスタックオーバーフローが起きて強制終了してしまうという事態に。驚くべきことに、過去にコピペしたクイックソートもどきは、速度を犠牲にしてこれを回避したコードだったのだ (多分)！THE 勘違い
さすがに強制終了してしまうのを放置するわけにもいかず、とはいえクイックソートもどきは速度に難がある。なら他のソートアルゴリズムを探そうか、と Wikipedia のソートの項目を見てみたところ、コムソートという聞き慣れないものを発見。詳しく見てみると、平均計算時間は O(n log n) と優秀で、しかも再帰が必要ない。早速テストしてみた結果、速度こそクイックソートに比べれば劣るものの、クイックソートもどきとはまだ比較にならないほど速いし、何よりスタック領域が不足することが絶対にない。というわけでコムソートを採用することに決定。
で、このコムソートって、実は VB6 にすごく適したソートアルゴリズムなんじゃないかな、と思った。再帰を使わないので安全だし、コードもシンプル、そして十分な速度もある (最速というわけではないけど、VB6 って時点で極端な高速化は諦めているようなものだし)。欠点は・・・知名度が低すぎる、くらいかな。ソートで検索すると上位に出てくるソートアルゴリズムを比較するサイトには載っていないし、ヒット数もクイックソートの40万件弱に対してコムソートの900件弱はあまりにも悲惨。というわけで、みんなでバンバン使って知名度を上げていきましょう。ご一緒に VB6 もいかがですか？
最後に uBMplay の話に戻るけど、まだ修正すべき部分が多々あるのと、追加・変更した部分のデバッグが済んでいないのでリリースはまだまだ先になります。気長にお待ちください。
おまけ: 特に書く必要もないと思うけどコード。Swap は二つの変数の中身を交換する関数。途中にあるコメントの入った行はコムソート11のための判定行。この行をコメントアウトすれば普通のコムソートになります。
Public Sub CombSort(ByRef array() As Variant)
Dim i As Long
Dim gap As Long
Dim max As Long
Dim flag As Long
gap = Int(UBound(array) / 1.3)
Do
If gap < 1 Then gap = 1
If gap = 9 Or gap = 10 Then gap = 11 'Comb Sort 11
flag = 0
max = UBound(array) - gap
For i = 0 To max
If array(i) > array(i + gap) Then
Call Swap(array(i), array(i + gap))
flag = i
End If
Next i
gap = Int(gap / 1.3)
Loop While (gap > 0 Or flag <> 0)
End Sub