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

整列アルゴリズムのひとつ。
挿入ソートの改良版で、Donald L. Shell（Communications of the ACM, 2:30-31, 1959）による整列法。高速だが、安定ではない。

挿入ソートは、ほとんど整列されたデータに関しては高速である。しかし、隣通しの交換しかしないため、あまり整列されていないデータでは低速であった。そこで、適当な間隔をあけて大雑把な整列を行うことで高速化させている。 大雑把な整列をするための間隔はいくつか考えられるが、下記の例ではh(1)=1, h(n)=3×h(n-1)+1で定義される数列を用いており、このときの実行時間はO(n^1.25)であることが知られている。

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

TypeDef keytype = Integer
Sub shelsort(n As Integer, a As *keytype)
Dim h As Integer, i As Integer, j As Integer
Dim x As keytype
h = 13
While h < n
h = 3 * h + 1
Wend
h = h / 9
While h > 0
For i = h To n
x = a[i]
j = i - h
While j >= 0 And a[j] > x
a[j + h] = a[j]
j = j - h
Wend
a[j + h] = x
Next i
h = h / 3
Wend
End Sub