応用情報技術者試験 令和6年度 春期 午前 問7

【正解】ア

バブルソートは、隣り合う二つの要素を比較し、順序が逆なら入れ替える操作を繰り返す整列方法です。アでは、数字列の末尾から先頭へ向かって比較し、小さい数字を前方へ移動させています。例えば「3、1、2」を末尾側から調べると、最初に1と2を比較してそのままとし、次に3と1を比較して入れ替えるので「1、3、2」になります。この1回の走査で最小値の1が先頭に確定します。未確定部分に同じ操作を繰り返せば、最終的に昇順になります。小さい値が泡のように端へ移動することから、バブルソートと呼ばれます。

イの方法は誤りです。これは、基準値を選び、それより小さいグループと大きいグループに分割して整列するクイックソートの説明です。 ウの方法は誤りです。これは、数字列を細かく分割した後、大小を比較しながら併合するマージソートの説明です。 エの方法は誤りです。これは、未処理部分から最小値を選び、未処理部分の先頭と交換する選択ソートの説明です。バブルソートのように隣接要素を順次交換する方法ではありません。

【ポイント】 バブルソートは「隣接する要素の比較と交換」、選択ソートは「最小値の選択」、クイックソートは「基準値による分割」で見分けます。 バブルソートの平均時間計算量はO（n²）であり、要素数が多い場合には効率が低下します。