応用情報技術者試験 令和5年秋 午前問6 解説付き過去問

この問題は、与えられた途中経過の状態変化から、使用された整列（ソート）アルゴリズムの種類を推測するものです。状態0から状態Nまでの推移の特徴を見て、どのアルゴリズムが該当するかを判断します。

1. 各状態の変化を確認
   データ列の状態が以下のように変化しています。

   状態0：3、5、9、6、1、2
   状態1：3、5、6、1、2、9
   状態2：3、5、1、2、6、9
   　・・・
   状態N：1、2、3、5、6、9

   この変化から、後ろにある最大値（9）が毎回1つずつ末尾に移動して固定されていく様子が見て取れます。

   また、すでに正しい位置にある末尾の値には手を加えず、前方の要素だけを操作しているように見えます。

   
   
   
2. バブルソートの特徴
   バブルソートは、隣接する要素を比較して、必要に応じて交換する操作を繰り返し、最大（または最小）の値を末尾に“バブル（泡）”のように押し上げていくアルゴリズムです。

   一回の走査（パス）で最大の要素が正しい位置に移動するため、繰り返すたびに末尾の要素が確定していきます。

   この動きは、今回の状態の変化と一致しています。

   
   
   
3. 他のソートとの違い
   ・挿入ソート：前の要素と比較して挿入し、左から順に整列していくため、右側のデータはあまり動かない。
   ・クイックソート：再帰的に分割していくため、局所的な並び替えではなく全体的な変化が見られる。
   ・ヒープソート：ヒープ木構造に変換するステップを伴い、特定の形に従った入れ替えが発生するため、今回のような逐次的な末尾確定の動きにはならない。
   
   
   

以上の観点から、今回の状態変化はバブルソートの特徴と一致するため、使用された整列アルゴリズムはバブルソートと判断できます。