ソートは並び替えの基本アルゴリズム。バブル・選択・挿入の3つは仕組みがシンプルで、試験頻出です。
日野 こむぎ
ソートって並び替えだよね。
どんな種類があるの?
藤森 さやか 先生
基本ソートは3種類覚えて。
バブルソート・選択ソート・挿入ソートよ。
青木 澪
どれも O(n²) で遅いけど、仕組みが単純で実装が簡単。
少量データならこれで十分ね。
日野 こむぎ
それぞれどう違うの?
藤森 さやか 先生
バブルは隣同士を比較して交換を繰り返す。
選択は毎回最小値を探して先頭に置く。
挿入はソート済み部分に1個ずつ正しい位置に挿入する。
桃井 すみれ
選択ソートが一番シンプルそうですぅ〜♪
青木 澪
計算量は同じだけど、データの状態によっては挿入ソートが速くなるのよ。
ほぼソート済みなら O(n) に近づくから。
日野 こむぎ
へぇ〜、データがキレイなら挿入ソートがお得ってこと?
藤森 さやか 先生
試験ではトレース問題 (1パスでどう変わるか) や、計算量を問う問題が多いわ。
具体的な配列で実際に手を動かして覚えるのがコツね。
同じ配列で3方式の動きを比較する
昇順に並べる配列 {5, 2, 4, 1} を使い、最初の処理単位を比べます。方式名だけでなく、どの要素を見て、どこへ動かすかを説明できるようにしましょう。
| 方式 | 最初の処理 | 処理後 | 見分ける語 |
|---|---|---|---|
| バブル | 左から隣接要素を比較し、逆順なら交換。1巡すると最大値5が右端へ移る | {2, 4, 1, 5} | 隣同士・交換・端へ確定 |
| 選択 | 未整列部分全体から最小値1を選び、先頭の5と交換する | {1, 2, 4, 5} | 最小値を探索・先頭と交換 |
| 挿入 | 先頭の5を整列済みとみなし、次の2を5の前へ挿入する | {2, 5, 4, 1} | 整列済み部分・ずらして挿入 |
選択ソートの結果だけが一度で完成形になっていますが、これは例の最小値が末尾にあり、交換後の残りも偶然整列していたためです。「1回で必ず全体が整列する」と一般化してはいけません。各方式とも、未確定部分を縮めながら処理を繰り返します。
試験問題での判断手順と誤答の原因
擬似コード問題では、最初に内側ループの仕事を見ます。隣接する添字を比較して交換するならバブル、未整列範囲を最後まで走査して最小位置を記録するなら選択、値を一時退避して大きい要素を1枠ずつ後方へずらすなら挿入です。名前を伏せられても、この三つの動作で判定できます。
計算量の設問では、要素数を n とすると比較回数がおおむね (n-1)+(n-2)+…+1 となるため、平均は3方式とも O(n²) です。ただし、ほぼ整列済みの入力に対し、交換・移動が不要なら早く打ち切る実装の挿入ソートは O(n) に近づきます。「平均計算量」と「最良計算量」を混同しないことが大切です。
よくある誤答は、「比較回数がO(n²)だから交換回数も必ず同じ」「同じ値の順序が必ず保たれる」と決めつけることです。安定性は実装条件に依存し、一般的な選択ソートは離れた要素を交換するため安定ではありません。設問が比較回数・交換回数・安定性のどれを尋ねているかを先に囲みましょう。
確認クイズ
次の3つの基本ソートの平均計算量として正しいものはどれか。
- 全てO(n)
- 全てO(n log n)
- 全てO(n²)
- 全てO(n³)
こたえを見る
正解: 3. 全てO(n²)
バブル・選択・挿入の3つの基本ソートはいずれも平均 O(n²) です。より高速なソートには O(n log n) のクイックソートやマージソートがあります。