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

問題本文

未整列の配列 A[i]（i=1, 2, …, n）を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。

選択肢

• ア.クイックソート
• イ.選択ソート
• ウ.挿入ソート
• エ.バブルソート

正解

エ. バブルソート

解説

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

選択肢ごとの解説

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