コムソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

整列アルゴリズムのひとつ。

コームソート、櫛ソートとも呼ばれる。バブルソートの改良版でStephen LaceyとRichard Boxが1991年4月に発表された。安定ではないが、実行速度は、ほぼO(n log n)になる。アルゴリズム的にはShellソートと同じように適当な間隔をあけて大雑把な整列をし、順次その間隔をつめていくことで高速化している。その間隔の数列は、データ総数を1.3で順次割った数列を使用する。また、間隔gap=9またはgap=10である時に強制的にgap=11とすることで、11以下の数列を11→8→6→4→3→2→1として効率を良くしたものをCombsort11と呼ぶ。

プログラミング掲示板「ソートロジック大会」なども参照のこと

TypeDef keytype = Integer
Const SHRINKFACTOR = 13
Sub combsort(n As Integer, a As *keytype)
Dim i As Integer, flg As Integer, gap As Integer
Dim limit As Integer, hold As Integer
gap = n * 10 / SHRINKFACTOR
Do
If gap = 0 Then gap = 1
'If gap = 9 Or gap = 10 Then gap = 11 'Combsort11の場合、この行を使用する
limit = n - gap + 1
flg = 0
i = 0
While i < limit
If a[i] > a[i + gap] Then
hold = a[i]
a[i] = a[i + gap]
a[i + gap] = hold
flg = i
End If
i = i + 1
Wend
gap = gap * 10 / SHRINKFACTOR
Loop While gap > 0 Or flg <> 0
End Sub