CO-K34｜情報Ⅰ 対策問題

正答

1

この問題のポイント

バブルソート（隣接交換による整列） を問う問題です。「隣どうしを比較して交換」がキーワードです。

解説

交換法(バブルソート)は、隣り合う2つの要素を比較し、順序が逆なら交換する操作を端から端まで繰り返す整列アルゴリズムです。たとえば[3,1,2]を昇順にするなら、3と1を比べて交換→[1,3,2]、3と2を比べて交換→[1,2,3]、という具合に進みます。

端から端まで比較・交換を通す1回分を「パス」といい、1回のパスが終わると最大値(または最小値)が端に確定します。値が泡(バブル)のように端へ浮かび上がっていくことが名前の由来です。パスをデータの個数分ほど繰り返せば、全体が整列します。

効率は良くありません。n個のデータに対して比較回数は最大でn(n−1)/2回、およそn²/2回です。n=10なら45回、n=100なら4950回と、データが10倍になると手間は約100倍に増えます。単純で理解しやすい反面、遅い——この特徴が選択法などとの比較で問われます。

共通テストでは「1回目のパスが終わった時点の並びはどれか」という途中経過の問題や、DNCLでバブルソートのプログラムを完成させる問題が定番です。「隣どうし」「交換」という言葉が見えたらバブルソートを疑いましょう。

選択肢の確認

1．○ 隣接する2要素の比較・交換を繰り返すのが交換法(バブルソート)。
2．× 二分探索は整列済みデータから探す探索アルゴリズムで、整列はしない。
3．× ハッシュ法はデータの保存場所を計算で求める技術。
4．× モンテカルロ法は乱数を使って値を推定する方法。

ここだけは覚えよう

バブルソート=隣どうし比較して逆なら交換 — 1パスごとに最大値が端に確定していく。