トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > シェルソート

挿入整列法を改良したソート手法。挿入整列法が隣の要素としか交換しないのに対し、
シェルソートではある程度離れた要素間で交換を行うことにより高速化する。

最悪計算量

O(N^3/2)

3

8

4

7

2

1

6

5

という配列があったとする。
まず間隔を仮に4として交換すると、(3,2),(8,1),(4,6),(7,5)という組み合わせで交換がおきる。

2

1

4

5

3

8

6

7

次に間隔を変更し2とすると、(2,4,3,6),(1,5,8,7)の組み合わせで交換する。

2

1

3

5

4

7

6

8

最後に間隔を1とすると、

1

2

3

4

5

6

7

8

と交換される。