応用情報技術者 2021年 秋期 午前2 問05

バブルソートの比較交換【午前2解説】

正解の理由

解法ステップ

1. 選択肢のキーワードを探す：「隣り合う」「比較」「入れ替え（交換）」「繰り返す」などを含むかを確認する。
2. アルゴリズムの典型的な動作を照合する：隣接比較＋交換→バブル、ピボットで区分→クイック、間隔を詰める→シェル、最小値取り出し→選択/ヒープ系。
3. 性質で確認：安定性や時間計算量などの知識と照らし合わせる（例：バブルは安定、$O(n^2)$）。
4. 上の対応で一致すればその選択肢を確定する（本問では隣接比較・交換の記述がある選択肢を選ぶ）。

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n-1-i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break
    return a

選択肢別の誤答解説

• ア: 「ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて...」
  → これはシェルソート（Shell sort）の特徴的な説明です。シェルソートはgapped insertion（間隔を置いた挿入）を繰り返す手法であり、バブルソートではありません。
• イ: 「中間的な基準値を決めて、それよりも大きな値と小さな値に振り分け...」
  → これはクイックソート（Quick sort）のパーティション操作の説明です。クイックソートは分割統治で再帰的に処理します。
• ウ: 「隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。」
  → これが典型的なバブルソートの説明です。配列を複数回走査し、各走査で隣接要素を交換していくことで大きい（または小さい）要素を端に「泡のように浮かせる」イメージが名前の由来です。
• エ: 「未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。」
  → これはヒープソート（Heap sort）や選択木（トーナメント木）を用いる手法の説明です。選択ソートと混同しがちですが、順序木（ヒープ）を使う説明はヒープソートに対応します。

よくある誤解

• バブルソートは「隣接比較」ではなく「挿入」の派生だと混同することがある。
  → 挿入ソートはある位置に要素を挿入することで整列を維持する手法で、バブルは隣接の交換を主体とする別のアルゴリズムです。
• 「1回の走査で整列が終わる」と誤解することがある。
  → バブルは複数パスが必要で、最悪では $O(n^2)$ の比較・交換が発生します。最良でも要素がほぼ整列されている場合を除き複数回の走査が必要です。
• 「バブルソートは常に無駄に遅い」と決めつけること。
  → 一定の条件下（ほぼ整列済み）で最適化（交換が発生しなければ早期終了）を行えば効果的に動作することがありますが、一般的な用途では効率が良くないのは事実です。

補足コラム

• バブルソートの派生や改良として「シェーカーソート（双方向バブル）」などがあります。これらは隣接交換の方向を変えて端から端へ往復することで一部の局面で改善しますが、計算量は依然として平均 $O(n^2)$ に近いです。
• シェルソートについて正確に述べると、シェルソートは「挿入ソートの改良版」であり、間隔（ギャップ）を置いた部分列に対して挿入ソートを行い、ギャップを小さくして最終的にギャップ1（通常の挿入ソート相当）にする手法です。以前の誤記述でシェルソートをバブルソートの改良版とする表現が見られましたが、正しくは挿入ソートをベースにした改良であることを押さえてください。

FAQ