テクノロジ系出題頻度 3/3
バブルソート
ばぶるそーと
定義
隣接要素を比較・交換しながら並べ替える単純なソート法。計算量はO(n²)。
詳細解説
隣り合う2要素を比較し、順序が逆なら交換する操作を繰り返す。大きい値が泡のように末尾へ浮かび上がるため命名。最悪・平均O(n²)、最良O(n)（既に整列済みかつ早期終了実装時）。安定ソート（同値要素の順序維持）でその場ソート（追加メモリ不要）だが、効率は悪く実用的にはほぼ使われない。教育目的でアルゴリズムの基本概念を学ぶ際に頻出。シェーカーソート（双方向）など改良版もある。
「バブルソート」が出る問題
関連用語
よくある質問
Q. バブルソートとは何ですか？
A. 隣接要素を比較・交換しながら並べ替える単純なソート法。計算量はO(n²)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。