シェルソート（Shell Sort）とは？

シェルソートは、挿入ソート（Insertion Sort）を改良したソートアルゴリズムです。一定の間隔（ギャップ）ごとに要素を比較・交換しながら並べ替え、徐々にその間隔を狭めて最終的に通常の挿入ソートを適用することで、高速化を図ります。

⸻

シェルソートの特徴 1. 部分的な挿入ソートの適用 • 通常の挿入ソートは、要素がほぼ整列していると高速に動作しますが、ランダムな並びのデータには遅い（最悪 O(n^2)）。 • シェルソートは、初めに要素間の距離を大きく取って並び替えることで、後半の挿入ソートがより高速に動作するようにします。2. 適切なギャップ（間隔）の選択が重要 • 例えば、最初は全体のサイズの半分の間隔で要素を並べ替え、次にその半分、さらに半分…と繰り返して最終的に間隔1（通常の挿入ソート）にします。3. 安定なソートではない • 挿入ソート自体は安定なソートですが、シェルソートは離れた要素を交換するため、順番が保持されないことがあります。

⸻

シェルソートのアルゴリズム 1. ギャップ（間隔）を決める • 例: h = n/2, n/4, \dots, 1 のように間隔を縮める。2. ギャップごとに挿入ソートを実行 • 間隔 h ごとに、通常の挿入ソートのように並び替えを行う。3. ギャップを縮めながら繰り返す • 最終的に間隔1（通常の挿入ソート）になった時点でソート完了。

⸻

実装（Go言語）

package main

import "fmt"

func shellSort(arr []int) {
	n := len(arr)
	// 初期ギャップを n/2 に設定し、1 になるまで半減
	for gap := n / 2; gap > 0; gap /= 2 {
		// ギャップごとの挿入ソート
		for i := gap; i < n; i++ {
			temp := arr[i]
			j := i
			// ギャップごとに比較しながら要素を移動
			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}
			arr[j] = temp
		}
	}
}

func main() {
	arr := []int{9, 8, 3, 7, 5, 6, 4, 1}
	fmt.Println("Before sorting:", arr)
	shellSort(arr)
	fmt.Println("After sorting:", arr)
}

⸻

時間計算量 • 最悪ケース: O(n^2)（単純な間隔の選び方の場合） • 平均ケース: O(n^{1.5}) から O(n \log n)（適切なギャップを選ぶ場合） • 最良ケース: O(n \log n)

補足: ギャップの選び方によってパフォーマンスが大きく変わる。 例えば、「Knuthの増加列」や「Hibbardの増加列」などが提案されている。

⸻

シェルソートのメリット・デメリット

メリット

✅ 挿入ソートよりも高速（特に大きな配列に対して有効） ✅ 簡単に実装可能 ✅ 追加のメモリを必要としない（in-place ソート）

デメリット

❌ 安定なソートではない（元の順序が保持されない可能性がある） ❌ ギャップの選び方によって性能が大きく変わる（最適なギャップ列の選択が難しい）

⸻

まとめ • シェルソートは、挿入ソートの改良版 で、大きな間隔で要素を交換することで高速化を実現。 • ギャップの選び方が重要 であり、適切なギャップ列を選ぶと O(n \log n) に近い速度が得られる。 • 安定なソートではない ため、安定性が求められる場面では適さない。

挿入ソートよりも一般的に高速だが、ギャップ選択次第で性能が変わる点が重要です。