応用情報技術者試験 応用情報技術者試験 令和3年度秋期 午前 問5: バブルソートの説明として，適切なものはどれか。

問題本文

バブルソートの説明として，適切なものはどれか。

選択肢

• ア.ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
• イ.中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の操作を繰り返す。
• ウ.隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
• エ.未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

正解

ウ. 隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

解説

代表的な整列アルゴリズムの特徴を区別する問題である。バブルソートは「隣り合う要素を比較し、大小の順序が望ましい並びと逆であれば入れ替える」という操作を繰り返して整列する手法で、1周ごとに最大値が末尾に確定していく。この説明に一致するのはウである。

選択肢ごとの解説

• ア.一定間隔おきの要素を整列し、間隔を1まで徐々に詰めていくのはシェルソートの説明である。
• イ.基準値（ピボット）を決めて大小2区分に振り分け、各区分内で同じ操作を再帰的に繰り返すのはクイックソートの説明である。
• ウ.正しい。隣り合う要素を比較し逆順なら交換する操作の繰り返しがバブルソートの定義そのものである。
• エ.未整列部分を順序木（ヒープ）にして最小値（または最大値）を取り出して整列済みに移すのはヒープソートの説明である。