「Shellソート」の編集履歴（バックアップ）一覧はこちら

「Shellソート」(2010/01/25 (月) 19:30:13) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

整列アルゴリズムのひとつ。
挿入ソートの改良版で、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)であることが知られている。 

プログラミング掲示板「ソートロジック大会」なども参照のこと 
#asciiart(blockquote){
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
}