応用情報技術者 2022年 秋期 午前2 問06

未整列配列の整列アルゴリズム判別【午前2 解説】

要点まとめ

• 結論：図の処理は隣接要素の比較と交換を繰り返すバブルソートの特徴を示しています。
• 根拠：内側ループで隣接要素を比較し、大小関係に応じて交換を行い、外側ループで全体を繰り返す構造です。
• 差がつくポイント：交換処理の具体的な手順とループの方向性、隣接要素比較の有無を正確に理解できるかが鍵です。

正解の理由

よくある誤解

解法ステップ

1. 内側ループの変数 $j$ が後ろから前へ減少していることを確認する。
2. 隣接要素 $A[j]$ と $A[j-1]$ の比較を行い、大小関係で交換処理を実施。
3. 交換処理後、再び隣接要素の比較に戻るループ構造を確認。
4. 外側ループ $i$ は1から $n-1$ まで増加し、全体の繰り返しを制御。
5. これらの特徴がバブルソートの典型的な動作であると判断。

選択肢別の誤答解説

• ア: クイックソート
  ピボット選択と分割再帰が特徴で、隣接要素の単純比較交換は行わない。
• イ: 選択ソート
  最小値を選んで先頭と交換するため、隣接要素の比較交換はしない。
• ウ: 挿入ソート
  挿入位置を探して要素を移動するが、内側ループは前から後ろへ進むのが一般的。
• エ: バブルソート
  隣接要素を比較し、条件に応じて交換を繰り返す典型的なアルゴリズム。

補足コラム

FAQ