バブルソートの特徴として適切なものはどれか。

📝 解説

バブルソートは隣り合う2要素を比較して順序が逆なら入れ替える操作を先頭から末尾まで繰り返すシンプルな整列アルゴリズムです。体育の身長順整列で「隣の人と比べて背が高ければ前に出て交換する」を端から端まで繰り返すイメージです。1回のパスで最大値が末尾に「泡（バブル）のように浮き上がる」ことからバブルソートと名付けられました。計算量は最悪・平均ともにO(n2)で、データ数が多いと急激に遅くなるため大規模データには不向きですが、アルゴリズムの仕組みが直感的で実装が容易なため、整列アルゴリズムの入門として世界中で教えられています。最良ケース（既に整列済み）では交換が発生しないためO(n)まで改善できます。誤答の「常にO(n log n)の計算量」はクイックソート・マージソートの平均計算量、「分割統治法を使った整列」はクイックソートやマージソートの説明、「常に最も効率的」という整列アルゴリズムは存在しません（それぞれ得意不得意がある）。「バブルソート＝隣接要素の比較・交換・計算量O(n2)」と覚えましょう！