令和3年度 高度共通 午前I（PM試験） 問3

正解：ウ

AI解説

バブルソートは、隣り合う要素同士を比較し、大小関係が逆であれば交換するという操作を繰り返して整列する単純なソートアルゴリズムである。「隣接要素の比較・交換の繰返し」が判断基準であり、ウが正しい。計算量は平均・最悪ともO(n²)である。 ア: 一定間隔おきに取り出した部分列を整列し、間隔を詰めながら繰り返すのはシェルソートの説明である。 イ: 基準値(ピボット)より大きい区分と小さい区分に振り分けて再帰的に整列するのはクイックソートの説明である。 ウ: 正しい。隣り合う要素の比較と交換を繰り返すのがバブルソートであり、小さい値が泡(バブル)のように浮き上がる様子が名前の由来である。 エ: 未整列部分を順序木(ヒープ)にして最小値を取り出す操作を繰り返すのはヒープソートの説明である。 💡 ソートは「隣同士=バブル」「間隔=シェル」「基準値で分割=クイック」「順序木=ヒープ」「最小値を選ぶ=選択」「適切な位置に挿す=挿入」とキーワード対応で即答できるようにする。