バブルソートとは？

詳細解説

バブルソート（Bubble Sort）は、隣接する2要素を比較し、大小の順序が逆であれば交換するという操作を配列の末尾まで繰り返すことで、最大値（または最小値）を順次末尾に移動させながら整列するアルゴリズムです。名称の由来は、小さな（大きな）値が泡（バブル）のように浮かび上がっていく様子からです。外側のループがn-1回、内側のループも最大n-1回実行されるため計算量はO(n²)であり、大規模データには不向きです。一方、実装が非常にシンプルで、**安定ソート**（同じ値の要素の相対順序が変化しない）という特性を持ちます。最適化として「ある1パスで交換が1度も発生しなければ整列完了」として早期終了できます。FE試験ではバブルソートの「何回目のパスで特定の要素がどこに移動するか」をトレースする問題が典型的です。また、選択ソート・挿入ソートとの比較（安定性・計算量の違い）も頻出論点です。

FE試験での出題ポイント

• 1計算量O(n²)：大規模データには非推奨
• 2安定ソート：同値要素の相対順序が保たれる
• 3最適化：1パスで交換なし→早期終了（最良O(n)）
• 4選択ソート・挿入ソートとの比較（3つのO(n²)ソートの差異）

関連用語