配列などのデータをある規則で並べ替えること。小→大が昇順、大→小が降順。
| 整列法 | 考え方（一言で） |
|---|---|
| 選択ソート（基本選択法） | 範囲内の最小値を選んで先頭へ置く、を繰返す |
| バブルソート（基本交換法） | 隣どうしを比較・交換して、大きい値を端へ運ぶ |
| 挿入ソート（基本挿入法） | 整列済みの中の正しい位置に挿入していく |
| 改良法 | もとの方法 | ポイント |
|---|---|---|
| ヒープソート | 選択法 | 木構造（ヒープ）で最大/最小を取り出す |
| シェーカーソート | バブル | 前後の両方向に交互にバブル |
| クイックソート | 交換法 | 基準値(ピボット)で大小2グループに分割、を繰返す |
| シェルソート | 挿入法 | 間隔をあけて整列→徐々に間隔を狭める |
| マージソート | ─ | 半分ずつに分割→整列しながら併合（マージ） |
| オーダ | 増え方 | n を10倍にすると手間は |
|---|---|---|
| O(n log n) | n 比例より少し多い程度 | 約10倍＋少し |
| O(n²) | n の2乗で急増 | 約100倍 |
主な整列法のオーダ：
| 整列法 | 比較回数 | オーダ | なぜそのオーダか |
|---|---|---|---|
| 交換法(バブル)・選択法・挿入法（基本3種） | n(n−1)/2 | O(n²) | 「n 個を n 回」の二重ループで総当たりするため |
| シェルソート | ─ | O(n^1.25〜1.5) | 挿入法を間隔をあけて行い、無駄な比較を減らした改良版 |
| クイック・ヒープ・マージ | n log₂n | O(n log n) | データを半分ずつに分割しながら整列するため（分割の深さが log n） |
Q1 ★バブルソートのトレース
データ列 5, 3, 8, 1 を昇順にバブルソート（隣どうし比較・交換）する。
1巡目が終わった時点の並びはどれか。
| 手順 | 並び |
|---|---|
| 初期 | 5 3 8 1 |
| 5,3比較 → 交換 | 3 5 8 1 |
| 5,8比較 → そのまま | 3 5 8 1 |
| 8,1比較 → 交換 | 3 5 1 8（最大値8が右端に確定） |
正解：イ（3, 5, 1, 8）
隣どうしを左から比較し、左>右なら交換。1巡すると最大値が右端に確定する（上のトレース）。
▼速解法：バブルソートは1巡ごとに端に1つ確定する。「1巡目＝最大値が右端に来る」だけ覚えれば、全部並べ替えなくても答えが絞れる。
補足：同じ列でも選択ソート1巡目なら最小値1を選んで先頭と交換 → 1, 3, 8, 5。方式で結果が変わるのでどの方式かを必ず確認。
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」
Q2（H30秋 問6）★整列法の説明の区別（頻出）
クイックソートの処理方法を説明したものはどれか。
正解：ウ
▼速解法：キーワードで一発判定。「基準値で分割」＝クイック／「最小値を選ぶ」＝選択／「正しい位置に挿入」＝挿入／「隣を交換」＝バブル。
Q3 ★選択ソートのトレース
5, 3, 8, 1 を選択ソート（最小値を先頭へ）で昇順に整列する。1巡目が終わった時点の並びはどれか。
正解：イ（1, 3, 8, 5）
選択ソート1巡目は、全体の最小値 1 を選んで先頭要素 5 と交換する → 1, 3, 8, 5。
| 巡 | 操作 | 並び |
|---|---|---|
| 1巡目 | 最小値 1 を先頭へ | 1, 3, 8, 5 |
| 2巡目 | 残り(3,8,5)の最小 3 は既に位置 | 1, 3, 8, 5 |
| 3巡目 | 残り(8,5)の最小 5 を前へ | 1, 3, 5, 8 |
参考：同じ列でもバブルソート1巡目は 3, 5, 1, 8（Q1参照）。方式によって途中経過が違う点に注意。
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」
Q4 ★バブルソートのトレース（2巡目）
次のデータをバブルソート（隣どうしを比較し、左＞右なら交換）で昇順に並べ替える。2巡目が終わった時点の並びはどれか。
正解：ア（3, 1, 4, 5, 8）
1巡目（最大 8 が右端へ確定）：
2巡目（次に大きい 5 が確定）：
→ 2巡目終了時は 3, 1, 4, 5, 8。ウ（3,5,1,4,8）は1巡目終了時なので混同に注意。
▼速解法：バブルソートは1巡ごとに端へ1つ確定。「何巡目か」＝確定した個数。全部を並べ替えなくても、確定していく端から答えを絞れる。
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」