共通テスト情報Ⅰ・4-12

整列アルゴリズムの一問一答

共通テスト「情報Ⅰ」の「アルゴリズムとプログラミング」から、整列アルゴリズムに関する4択問題を10問。「答えと解説を見る」を開くと、正解とその理由がその場で読めます。会員登録は不要です。

この分野の演習

全10問／解説付き・基本無料

アプリ形式で解く（全800問）アルゴリズムとプログラミングの要点解説を読む

問題

上から順に解いてみてください。答えは各問の下で確認できます。

問14-12・基礎

隣り合うデータを比較し、順序が逆であれば入れ替えるという操作を、データの端から端まで繰り返す単純なソート手法はどれか？

①選択ソート（選択法）
②挿入ソート（挿入法）
③バブルソート（交換法）
④マージソート（併合法）

答えと解説を見る

正解 ③バブルソート（交換法）

解説
正解は「バブルソート（交換法）」。となりどうしを比べ、順が逆なら入れ替えることを繰り返す方法。

なぜ
1回端まで比べ終えると、いちばん大きい値（または小さい値）が端に移って確定する。泡（バブル）が水面に上がるように見えることが名前の由来。仕組みは簡単だが、基本の形では比べる回数が n(n−1)/2 回（5個なら10回）と多い。

ひっかけ注意

・「選択ソート（選択法）」…残りの中から最小値を探し、未整列部分の先頭と入れ替える方法。1周で入れ替えは多くても1回。
・「挿入ソート（挿入法）」…整列ずみの部分に、次のデータを正しい位置へ差しこむ方法。既に並んでいれば比較は n−1 回で済む。
・「マージソート（併合法）」…半分に分けて整列し、2つの列を合わせながら並べる方法。並び方によらず計算量は O(n log n)。

問24-12・基礎

未整列のデータの中から「最小値（または最大値）」を見つけ出し、それを未整列部分の先頭と交換する操作を繰り返す手法はどれか？

①バブルソート（交換法）
②挿入ソート（挿入法）
③クイックソート
④選択ソート（選択法）

答えと解説を見る

正解 ④選択ソート（選択法）

解説
正解は「選択ソート（選択法）」。まだ並んでいない部分から最小値を選び、その先頭と入れ替える方法。

なぜ
1回ごとに1つずつ正しい位置が決まる。N 個なら最小値を探す処理を N−1 回行う。最小値を探すために残りをすべて比べるので、比べる回数は並び方に関係なく n(n−1)/2 回で同じ。

ひっかけ注意

・「バブルソート（交換法）」…最小値を探すのではなく、となりどうしを比べて順が逆なら入れ替える方法。入れ替えの回数は、大小が逆の組の数と同じ。
・「挿入ソート（挿入法）」…次のデータを、整列ずみの部分の正しい位置に差しこむ方法。昇順に並んでいれば比較は n−1 回。
・「クイックソート」…基準値より小さいか大きいかで2つに分け、それぞれを整列する方法。先頭を基準値にすると、整列済みのデータでは比較が n(n−1)/2 回に増える。

問34-12・基礎

整列済みのデータ列に対して、新しいデータを適切な位置に「差し込む」ことで整列範囲を広げていく手法はどれか？

①挿入ソート（挿入法）
②選択ソート（選択法）
③バブルソート（交換法）
④シェルソート

答えと解説を見る

正解 ①挿入ソート（挿入法）

解説
正解は「挿入ソート（挿入法）」。トランプの手札を並べるように、次の1枚を正しい位置に差しこんでいく方法。

なぜ
整列ずみの部分を後ろから見ていき、入れる値より大きいものを1つずつ後ろにずらして空いた場所に入れる。もともとほぼ並んでいるデータなら、ずらす回数が少なく速く終わる。

ひっかけ注意

・「選択ソート（選択法）」…残りから最小値を選び、先頭と入れ替える方法。比較回数は並び方によらず n(n−1)/2 回。
・「バブルソート（交換法）」…となりどうしを比べて、順が逆なら入れ替える方法。1周ごとに最大値が右端に決まる。
・「シェルソート」…間をあけた要素どうしで挿入ソートを行い、間隔を縮めていく改良版。最後は間隔1の挿入ソートになる。

問44-12・基礎

データを基準値（ピボット）より小さいグループと大きいグループに分割し、それぞれを再帰的に整列させる高速な手法はどれか？

①バブルソート
②クイックソート
③ヒープソート
④基数ソート

答えと解説を見る

正解 ②クイックソート

解説
正解は「クイックソート」。基準値（ピボット）で2つのグループに分け、それぞれに同じことを繰り返す方法。

なぜ
分けるたびに、基準値はその時点で正しい位置に決まる。うまく半分ずつ分かれれば速く、平均の計算量は O(n log n)。ただし分け方がかたよると最悪 O(n²) になる。文部科学省の教員研修用教材も、逆順に並んでいる場合などは比較の回数が膨大になり、選択ソートより時間がかかることもあると説明している。

ひっかけ注意

・「バブルソート」…となりどうしを比べて入れ替える方法で、グループに分けない。基本の形では比較は n(n−1)/2 回。
・「ヒープソート」…ヒープという木（親が子より大きい）の根から、最大値を1つずつ取り出して並べる方法。最悪の場合でも O(n log n)。
・「基数ソート」…値どうしを比べずに、1の位、10の位のように桁ごとに分けて並べる方法。桁数の決まった整数などに使える。

問54-12・基礎

データを半分ずつに分割し、それぞれを整列させてから、整列済みのデータを「合体」させて全体を整列させる手法はどれか？

①クイックソート
②シェルソート
③マージソート（併合法）
④ヒープソート

答えと解説を見る

正解 ③マージソート（併合法）

解説
正解は「マージソート（併合法）」。分けて整列し、2つの整列ずみの列を合わせながら1つにする方法。

なぜ
2つの列の先頭どうしを比べ、小さいほうから順に取り出せば、合わせた列も整列する（これをマージという）。データの並び方によらず O(n log n) で動く。

ひっかけ注意

・「クイックソート」…基準値で分けるのが中心で、分けたあとに合わせる作業はない。分け方がかたよると n(n−1)/2 回比べる。
・「シェルソート」…間隔をあけて挿入ソートを行い、間隔を縮めていく方法。最後は間隔1の挿入ソートになる。
・「ヒープソート」…ヒープ（親が子より大きい木）の根から、最大値を1つずつ取り出す方法。2つの列を合わせる作業は使わない。

問64-12・標準

親の値が子の値より常に大きい（または常に小さい）という条件を満たす木構造を利用して、最大値（または最小値）を順次取り出すソート手法はどれか？

①ツリーソート
②バケットソート
③クイックソート
④ヒープソート

答えと解説を見る

正解 ④ヒープソート

解説
正解は「ヒープソート」。親が子より常に大きい（小さい）木をヒープといい、これを使って並べる方法。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
ヒープでは、根にいつも最大値（最小値）がある。根を取り出し、残りでヒープを作り直すことを繰り返すと、大きい順（小さい順）に取り出せる。並び方によらず O(n log n) で動く。

ひっかけ注意

・「ツリーソート」…二分探索木（左の子に小さい値、右の子に大きい値）に入れてから小さい順にたどる方法。ヒープとの違いは、親子の上下ではなく左右の位置で大小を決める点。
・「バケットソート」…値の範囲ごとの入れ物（バケツ）に分けて並べる方法。0〜9、10〜19のように範囲で分ける。
・「クイックソート」…基準値より小さいか大きいかで分ける方法で、木構造は使わない。平均では速いが、並び方によっては n(n−1)/2 回比べる。

問74-12・標準

同じ値を持つデータが複数ある場合、ソート前後でそれらの元の並び順が変わらないことが保証される性質を何と呼ぶか？

①安定なソート（安定性）
②高速なソート
③内部ソート
④再帰的ソート

答えと解説を見る

正解 ①安定なソート（安定性）

解説
正解は「安定なソート（安定性）」。同じ値のデータどうしの前後関係が、並べ替えたあとも保たれる性質。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
例えば出席番号順の名簿を点数順に並べ替えたとき、同じ点数の人が出席番号順のままなら安定。挿入ソート・バブルソート・マージソートはふつうの書き方で安定だが、選択ソート・クイックソート・ヒープソートは同じ値の順番が入れ替わることがある。

ひっかけ注意

・「高速なソート」…比較の回数が少なく速いこと。速いクイックソートでも、同じ値の順番が入れ替わる場合がある。
・「内部ソート」…主記憶装置（メモリ）の中だけで並べ替えるソート。データが大きく補助記憶装置も使う場合は外部ソートという。
・「再帰的ソート」…自分自身を呼び出して並べ替える方法。再帰を使うマージソートは安定だが、同じく再帰を使うクイックソートは安定とは限らないため、再帰かどうかは安定性と関係がない。

問84-12・標準

図は、バブルソートで 5, 4, 3, 2, 1 を小さい順に並べたときの、各巡の後の並びである。バブルソートで、データ数 N=5 の場合（例：5, 4, 3, 2, 1）、すべての並べ替えを完了するために必要な最大の比較回数はいくつか？

自作の図

①5回 (N回)
②10回 (4+3+2+1)
③20回 (N×(N-1))
④25回 (N²回)

答えと解説を見る

正解 ②10回 (4+3+2+1)

解説
正解は「10回 (4+3+2+1)」。一般に N(N−1)/2 回で、N＝5 なら 5×4÷2＝10。

手順
①図の①（1巡目）は5個の中で4回比べ、最大値が右端に決まる。
②2巡目は残り4個で3回、3巡目は2回、4巡目は1回比べる。
③合計は 4＋3＋2＋1＝10回。基本の形のバブルソートは、並び方によらずこの回数だけ比べる。

ひっかけ注意

・「5回 (N回)」…1巡目の4回と2巡目の1回分にしかならない。5, 4, 3, 2, 1 では入れ替えだけでも10回必要。
・「20回 (N×(N-1))」…2で割るのを忘れた値。1番目と2番目のような同じ組を、2回数えてしまっている。
・「25回 (N²回)」…オーダーが O(N²) であることと、実際の回数を取り違えた値。O(N²) は増え方の目安で、N が2倍なら回数がおよそ4倍になるという意味。

問94-12・標準

クイックソートやマージソートのように、大きな問題を小さな問題に分割して解き、それらを統合して全体の解を得るアルゴリズムの考え方を何と呼ぶか？

①動的計画法
②貪欲法（グリーディ法）
③分割統治法
④バックトラック法

答えと解説を見る

正解 ③分割統治法

解説
正解は「分割統治法」。大きな問題を同じ形の小さな問題に分けて解き、答えを合わせる考え方。（情報Ⅰの範囲を少し超えた発展の内容です）

なぜ
小さく分けると1つ1つは簡単に解ける。マージソートは半分に分けて整列し合わせる、クイックソートは基準値で分けて整列する、という形でこの考え方を使う。自分自身を呼び出す再帰と相性がよい。

ひっかけ注意

・「動的計画法」…小さな問題の答えを表に記録して使い回し、同じ計算を繰り返さない方法。分けた問題どうしが重なる場合に向く。
・「貪欲法（グリーディ法）」…その場でいちばんよく見えるものを選び続ける方法。おつりを500円玉・100円玉のように大きい硬貨から順に払う考え方など。
・「バックトラック法」…候補を順に試し、行きづまったら1つ前にもどって別の候補を試す方法。迷路やパズルを解くときに使う。

問104-12・基礎

アルゴリズムの計算量において、データ数Nが2倍になったとき、処理時間が「4倍」になるオーダーはどれか？

①O(N)
②O(log N)
③O(N³)
④O(N²)

答えと解説を見る

正解 ④O(N²)

解説
正解は「O(N²)」。N が2倍になると N² は 2×2＝4倍になる。

手順
①N を 2N に置き換える。
②(2N)² ＝ 4N² なので、処理時間は4倍。
③同じように N が10倍なら100倍になる。バブルソートや選択ソートの比較回数がこの増え方。

ひっかけ注意

・「O(N)」…N が2倍なら処理時間も2倍。線形探索の最大の比較回数がこの増え方。
・「O(log N)」…N が2倍になっても、log₂N は1増えるだけ。二分探索の最大の比較回数がこの増え方。
・「O(N³)」…N が2倍なら 2×2×2＝8倍になる。三重の繰り返しで N×N×N 回処理する場合。

当サイトは、独立行政法人大学入試センターとは一切関係のない、非公式の学習サイトです。試験に関する最新情報は、大学入試センターの公式サイトでご確認ください。

共通テスト情報Ⅰ 基礎完全対策（全800問）に戻る

※本ページでは、アクセス解析（Googleアナリティクス）と、広告の配信・成果の計測（A8.net）のためにCookie等を利用し、閲覧に関する情報をGoogle LLC・株式会社ファンコミュニケーションズへ送信しています。詳しくはプライバシーポリシーをご覧ください。

※本ページの問題・解説は、生成AI（人工知能）を活用して作成しています。