応用情報技術者試験 応用情報技術者試験 令和4年度秋期 午前 問6: 未整列の配列 A[i]（i=1, 2, …, n）を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。

正解

エ. バブルソート

正答率 51.2%（527人中 270人が正解）

問題の解説

流れ図の構造から整列アルゴリズムの種類を判定する問題。内側のループ2は j を n から i+1 まで1ずつ減らしながら、隣り合う要素 A[j] と A[j−1] を比較し、A[j] が小さければ作業用変数 w を使って交換している。このように隣接要素の比較・交換を繰り返して小さい値を泡のように前方へ運ぶ手法はバブルソートである。外側ループ1で確定範囲を1つずつ狭めていく点もバブルソートの特徴であり、正解はエである。

選択肢ごとの解説

• アクイックソートは基準値(ピボット)を決めて大小2グループに分割する分割統治法で、隣接要素の比較交換を繰り返す本図の構造とは異なるので誤り。
• イ選択ソートは未整列部分から最小値を探してその位置と交換する手法であり、隣接比較ではなく最小値探索が中心になるため本図とは異なり誤り。
• ウ挿入ソートは着目要素を整列済みの左側の適切な位置へ挿入する手法だが、本図は隣接する2要素の比較・交換を末尾側から繰り返す典型的なバブルソートの動作なので、挿入ソートは誤り。
• エ正しい。隣り合う A[j] と A[j−1] を比較し小さい方を前へ送る交換を二重ループで繰り返す動作はバブルソートそのものである。