ここでは ヒープソート（Heap Sort） と シェルソート（Shell Sort） を、
プログラミング初心者でもイメージしやすい 図解（ASCIIアート） で分かりやすく説明します。
ヒープソート（Heap Sort）の図解
ヒープソートとは？
- 配列を ヒープ（完全二分木） の形にして並べ替えるソート
- ヒープは「親 ≥ 子」が成り立つ 最大ヒープ を使う
- 最大値を根（先頭）に持つ → それを後ろへ送る → またヒープ化 … を繰り返す
1. 配列をヒープ（最大ヒープ）にする
例の配列：
[4, 10, 3, 5, 1]
ツリーとして見ると：
4
/ \
10 3
/ \
5 1
最大ヒープになるように「親 ≥ 子」になるまで下げたり上げたりする（heapify）。
最大ヒープ化後：
10
/ \
5 3
/ \
4 1
→ 配列は：
[10, 5, 3, 4, 1]
2. 先頭（最大値）を末尾と交換
[10, 5, 3, 4, 1]
↓ swap
[1, 5, 3, 4, 10] ← 10 が確定ポジションへ移る
3. 残りをまたヒープ化
[1, 5, 3, 4] + [10]
最大ヒープ化：
[5, 4, 3, 1, 10]
4. また先頭と末尾（未確定部分）を交換
[5, 4, 3, 1, 10]
↓ swap
[1, 4, 3, 5, 10]
5. 同じ処理を繰り返すと…
最終的に：
[1, 3, 4, 5, 10]
ヒープソートの特徴まとめ
| 特徴 | 内容 |
|---|---|
| 計算量 | O(n log n)（安定して速い） |
| メモリ | 追加メモリほぼ不要（in-place） |
| 安定性 | 安定ソートではない |
| 向いている場面 | メモリを節約しつつ高速化したい |
シェルソート（Shell Sort）の図解
シェルソートとは？
- 挿入ソートを改良して 離れた要素同士を比較して並べる
- 最初は大きな「間隔」で並べ替え、徐々に間隔を狭めていく
- ほぼ整列状態にしてから最後に挿入ソートで仕上げる
シェルソートの動き（ギャップ法）
例の配列：
[8, 5, 3, 7, 6, 2]
ギャップ（間隔）を 3 → 1 として進める例：
① gap = 3
3つ離れた要素をグループとして並べ替え
グループ1: (0, 3) → 8 と 7 → 並べて [7, 5, 3, 8, 6, 2]
グループ2: (1, 4) → 5 と 6 → そのまま
グループ3: (2, 5) → 3 と 2 → 並べて [7, 5, 2, 8, 6, 3]
状態：
[7, 5, 2, 8, 6, 3]
② gap = 1（最後は通常の挿入ソート）
[7, 5, 2, 8, 6, 3]
↑ 挿入ソートする
→ [2, 3, 5, 6, 7, 8]
シェルソートの特徴まとめ
| 特徴 | 内容 |
|---|---|
| 計算量 | O(n log n) 〜 O(n^2)（ギャップ次第） |
| メモリ | 追加メモリ不要 |
| 安定性 | 安定ソートではない |
| 利点 | 実装が簡単なのに高速になりやすい |
| 実務での使用 | やや減少（クイックソート・マージソートが主流） |
4つのソートを図解で比較（初心者向けまとめ）
| ソート | 計算量 | 安定性 | 特徴 |
|---|---|---|---|
| 挿入ソート | O(n²) | 安定 | 小規模に強い・実装簡単 |
| マージソート | O(n log n) | 安定 | 分割→結合で確実に速い |
| ヒープソート | O(n log n) | 不安定 | メモリ少なく高速・堅実 |
| シェルソート | O(n¹〜²) | 不安定 | ギャップで高速化・実装簡単 |