バブルソートの記述はどれか｜科目A-1（応用情報技術者） 令和6年 春期午前試験 問7
出典：令和6年春期 午前 問7
分野：アルゴリズムとプログラミング ／ アルゴリズム
整列方法に関するアルゴリズムの記述のうち，バブルソートの記述はどれか。ここで，整列対象は重複のない1から9の数字がランダムに並んでいる数字列とする。
- ア：数字列の最後の数字から最初の数字に向かって，隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。
- イ：数字列の中からランダムに基準となる数を選び，基準より小さい数と大きい数の二つのグループに分け，それぞれのグループ内も同じ操作を繰り返し行う。
- ウ：数字列をほぼ同じ長さの二つの数字列のグループに分割していき，分割できなくなった時点から，グループ内で数字が小さい順に並べる操作を繰り返し行う。
- エ：未処理の数字列の中から最小値を探索し，未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。
TSUNAGARU-ADVICE
まず押さえたいこと
バブルソートは、隣り合う二つの要素を比較し、順序が逆なら入れ替える操作を繰り返す整列方法です。端から順に比較を続けることで、大きい値または小さい値が少しずつ端へ移動していきます。
迷ったときの判断軸
基準値を選んで大小に分割するのはクイックソート、半分ずつ分割してから併合するのはマージソート、未処理部分から最小値を探して先頭と入れ替えるのは選択ソートです。「隣同士を比較して入れ替える」ならバブルソートと整理しましょう。
科目Bにつなげるために
特にプロフェッショナルデジタルスキル（システム）試験合格を目指す方は、整列アルゴリズムを処理手順と計算量の違いで比較できるようにしましょう。バブルソート・選択ソート・クイックソート・マージソートの特徴を区別することが、アルゴリズム選択や性能評価にもつながります。
バブルソートは、隣り合う二つの要素を比較し、順序が逆であれば入れ替える操作を繰り返して整列する方法です。
例えば、小さい順に並べる場合は、隣接する二つの数字を比較し、大きい方が後ろに来るように入れ替えていきます。この操作を数字列全体に対して繰り返すことで、最終的に昇順に整列されます。
したがって、アが適切です。
❌他選択肢が誤りの理由イ：数字列の中からランダムに基準となる数を選び，基準より小さい数と大きい数の二つのグループに分け，それぞれのグループ内も同じ操作を繰り返し行う。
⇒クイックソートの説明です。基準値であるピボットを選び、それより小さいグループと大きいグループに分割して、それぞれを再帰的に整列します。
ウ：数字列をほぼ同じ長さの二つの数字列のグループに分割していき，分割できなくなった時点から，グループ内で数字が小さい順に並べる操作を繰り返し行う。
⇒マージソートの説明です。数字列を分割していき、要素数が1になるまで分けた後、小さい順になるように併合していきます。
エ：未処理の数字列の中から最小値を探索し，未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。
⇒選択ソートの説明です。未整列部分から最小値を探し、その最小値を未整列部分の先頭と交換する操作を繰り返します。