基本情報技術者 一問一答｜A 第51問

解説

バブルソートは、隣接する2要素の大小を比較して順序が逆なら交換する操作を繰り返し、整列を完成させる単純なソートアルゴリズムである。要素数nのとき比較回数は最大で(n−1)＋(n−2)＋…＋1＝n(n−1)/2回となり、計算量のオーダーはO(n²)である。例えばnが10倍になると処理時間は約100倍に増える。O(n log n)はクイックソート・マージソート・ヒープソートなど高速なソートの計算量であり、O(n)は全要素を1回走査する程度の処理、O(log n)は二分探索の計算量に相当するため、いずれもバブルソートの最悪計算量ではない。基本情報技術者試験では各ソートアルゴリズムと計算量の対応（単純な交換・選択・挿入ソートはO(n²)、高速なソートはO(n log n)）が頻出である。