バブルソートの平均計算量はどれか？

📝 解説

バブルソートは「隣り合う2要素を比較して、順序が逆なら入れ替える」操作を全体に対して繰り返すソートアルゴリズムです。体育の整列で「隣の人と背の順を確認しながら端から端まで交換を繰り返す」動作に似ています。n個のデータに対して、1回のパスで最大n-1回の比較、それをn-1回繰り返すため、計算量は最悪も平均もO(n²)です。バブルソートの特徴は「実装がとてもシンプル」「データの大きい要素が泡のように末尾へ浮き上がる」「既にほぼ整列済みのデータに対してはO(n)に近い性能が出る」という点です。ただし大規模データには非効率で実用には向きません。マージソートやクイックソートのO(n log n)と比べると、n＝1000なら約100万対約1万回の比較で圧倒的な差があります。「バブルソート＝O(n²)」はアルゴリズム学習の基礎知識として確実に覚えましょう！