平成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]の値の入替えは何回行われるか。
- ア 3
- イ 6
- ウ 8
- エ 15
解答・解説を見る
正解：ウ
AI解説
正解はウ(8回)。隣接要素を比較して入れ替えるバブルソートの交換回数は、初期配列の転倒数(前にある要素の方が大きい組の数)に等しい。21,5,53,71,3,17について各要素より後ろにあるより小さい要素を数えると、21の後ろに5,3,17の3個、5の後ろに3の1個、53の後ろに3,17の2個、71の後ろに3,17の2個、3と17は0個。合計3+1+2+2=8回の交換が行われる。 ア: 3は一部の要素(例えば21)に関する転倒だけを数えた値である。 イ: 6は転倒の組を数え落とした値である。 ウ: 正しい。転倒数の合計は8であり、交換は8回行われる。 エ: 15はn=6の全組合せ数6×5÷2=15であり、比較回数の最大値と混同した値である。 💡 バブルソート(隣接交換ソート)の交換回数=転倒数は頻出の性質。各要素について「自分より後ろにある小さい要素の個数」を数えて合計すればよい。
出典：平成25年度 秋期 応用情報技術者試験 午前 問9 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。