CO-K35｜情報Ⅰ 対策問題

正答

1

この問題のポイント

選択ソート（最小値を選んで交換） を問う問題です。バブルソートとの手順の違いを言えるようにしましょう。

解説

選択法(選択ソート)は、次の2手順の繰り返しで整列するアルゴリズムです。

1. まだ整列していない部分の中から最小値を探す。
2. その最小値を、未整列部分の先頭の要素と交換する。

これで先頭から1つずつ「確定済み」が増えていきます。たとえば[3,1,2]なら、全体の最小値1を先頭の3と交換→[1,3,2]、残り[3,2]の最小値2を3と交換→[1,2,3]で完成です。

このアルゴリズムの面白さは、「最小値を求める」という基本アルゴリズムを部品として組み込んでいることです。学んだアルゴリズムを組み合わせて新しいアルゴリズムを作る、という積み上げの好例になっています。

バブルソートとの対比も出題されます。比較回数はどちらも約n²/2回ですが、交換回数は選択法の方が少ない(1周につき最大1回、全体で最大n−1回)のが特徴です。「隣どうしを何度も交換=バブルソート、最小値を探して1回交換=選択ソート」と手順の言葉で見分けましょう。

選択肢の確認

1．○ 未整列部分の最小値を先頭と交換する操作の繰り返しが選択法。
2．× 交換法(バブルソート)は隣接要素の比較・交換を繰り返す方法。
3．× 線形探索は先頭から順に探す探索法で、整列はしない。
4．× 逐次翻訳はインタプリタの動作の説明。

ここだけは覚えよう

選択ソート=最小値を探して先頭と交換 — 交換回数が少ない(最大n−1回)のが特徴。