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

この問題は、未整列の配列を整列するフローチャートから、使用されている整列アルゴリズムを特定するものです。

1. バブルソートの基本動作
   バブルソートは、隣接する要素同士を比較し、順序が逆であれば交換することを繰り返す単純な整列アルゴリズムです。
   要素を比較して順に後方へ移動させていく様子が、水面に気泡（バブル）が浮かぶようであることからこの名前が付けられています。
   計算量は最悪で n2 です。
   
   
2. 流れ図に見られる特徴的処理
   流れ図では、A[j] ← A[j-1] と A[j-1] ← w のように、隣り合う要素を変数wを用いて入れ替える処理が繰り返されています。
   このような処理は、バブルソート特有の「隣接要素の比較と交換」に該当し、他のソートとは異なる特徴です。
   
   
3. 他の整列アルゴリズムとの違い
   
   1. クイックソート：基準値（ピボット）を用いて配列を2分割し、それぞれを再帰的に整列します。
   2. 選択ソート：未整列部分から最小（または最大）値を探し、先頭と交換します。
   3. 挿入ソート：未整列部分の要素を整列済み部分に1つずつ挿入します。
   これらはいずれも「隣接要素をその場で交換する」バブルソートとは異なる動作をします。
   
   

したがって、与えられたフローチャートで使われている整列アルゴリズムはバブルソートです。