平成25年度 秋期 応用情報技術者試験 午前 問9
テクノロジ／アルゴリズム未整列の配列a[i]（i＝1，2，…，n）を，流れ図で示すアルゴリズムによって昇順に整列する。n＝6でa[1]～a[6]の値がそれぞれ，21，5，53，71，3，17の場合，流れ図において，a[j－1]とa[j]の値の入替えは何回行われるか。
出典：平成25年度 秋期 応用情報技術者試験 午前 問9
- ア3
- イ6
- ウ8
- エ15
正解：ウ
解説
この流れ図はバブルソートです。n＝6，初期値21，5，53，71，3，17に対してループ1（i＝1～5），ループ2（j＝n～i＋1）で隣接要素を比較し，a[j－1]＞a[j]のときだけ入れ替えます。実際にトレースすると，入替えは合計8回発生します。
選択肢ごとの解説
- ア誤り。3回は，比較回数と入替え回数を混同したり，一部のパスだけをトレースした場合に出やすい値です。
- イ誤り。6回は，途中のパスで入れ替えが不要だった箇所を数え漏らした場合に出やすい値です。
- ウ正しい。全てのパスをトレースすると，入替えは合計8回行われます。
- エ誤り。15回は比較（判定）の回数と入替えの回数を取り違えた場合に近い値です。