バブル・選択・挿入・クイック・マージソートを10問で比較します。手順を紙に書いてから解説を開き、どの位置が確定するかを確認しましょう。学習用のオリジナル問題です。
解く前の確認
途中状態は走査方向や交換方式で変わります。計算量も最良・平均・最悪を分け、実装条件を確認しましょう。
第1問
配列 7, 3, 5, 2 に対して、昇順のバブルソートを1回（先頭から末尾まで1巡）行った後の配列はどれか。
A. 3, 5, 2, 7
B. 2, 3, 5, 7
C. 3, 7, 2, 5
D. 7, 3, 2, 5
第1問の解答・解説を見る
答え：A
1巡すると、
- 7と3 → 交換
- 7と5 → 交換
- 7と2 → 交換
→ 3, 5, 2, 7
バブルソートは最大値が末尾へ移動します。
第2問
未整列部分から最小値を選び、整列済み部分の末尾に配置していく方式はどれか。
A. バブルソート
B. 選択ソート
C. 挿入ソート
D. クイックソート
第2問の解答・解説を見る
答え：B
未整列部分から最小値を選んで先頭側に確定していくのが選択ソートです。
第3問
挿入ソートの特徴として最も適切なものはどれか。
A. 基準値で分割しながら整列する
B. 左側を整列済みとして要素を適切な位置に挿入する
C. 毎回最大値を末尾へ送る
D. 半分に分割して最後に併合する
第3問の解答・解説を見る
答え：B
挿入ソートは、左側を整列済みとして現在の要素を正しい位置へ差し込みます。
トランプを並べる感覚です。
第4問
平均計算量が O(nlogn) となるものはどれか。
A. バブルソート
B. 選択ソート
C. クイックソート
D. 挿入ソート
第4問の解答・解説を見る
正解：C。一般的なクイックソートの平均時間計算量はO(n log n)、最悪はO(n²)です。他の選択肢の基本形は平均O(n²)ですが、挿入ソートなどの最良時まで同じとは限りません。
第5問
配列 8, 4, 6, 2 に対して未整列部分の最小値を先頭要素と交換する選択ソートの最初の1回を行った後の配列はどれか。
A. 4, 8, 6, 2
B. 6, 4, 8, 2
C. 2, 4, 6, 8
D. 2, 4, 8, 6
第5問の解答・解説を見る
答え：C
ここ、試験で大事なポイントです。
配列 8, 4, 6, 2 の未整列部分全体から最小値 2 を探し、先頭の 8 と交換します。
→ 2, 4, 6, 8
ただし、1回でたまたま全体が整列しただけです。
選択ソートの1回は「先頭が確定する」処理です。
第6問
クイックソートに関する説明として正しいものはどれか。
A. 必ず O(nlogn) になる
B. 基準値の選び方によって性能が変わる
C. 隣接要素だけを交換する
D. 追加の配列領域が必須である
第6問の解答・解説を見る
答え：B
クイックソートは 基準値の選び方で分割効率が変わります。
偏ると 最悪 O(n²) になります。
第7問
配列 4, 2, 5, 3 に対して挿入ソートで2番目の要素まで処理した時点の状態はどれか。
A. 2, 4, 5, 3
B. 4, 2, 5, 3
C. 2, 5, 4, 3
D. 2, 3, 4, 5
第7問の解答・解説を見る
答え：A
4, 2, 5, 3
2番目の要素 2 を左側に挿入。
→ 2, 4, 5, 3
ここでは左側2要素が整列済みになります。
第8問
マージソートの特徴として適切なものはどれか。
A. 隣接要素の交換を繰り返す
B. 未整列部分から最大値を選択する
C. 配列を分割し、整列後に併合する
D. 先頭から順に適切位置へ挿入する
第8問の解答・解説を見る
答え：C
マージソートは
- 半分に分割
- それぞれ整列
- 最後に併合
という流れです。
第9問
次の説明に対応する基本ソートはどれか。「左側の整列済み部分へ順に要素を挿入する。配列が既に昇順なら、各要素は直前の要素との確認で済み、最良時間計算量はO(n)になる。」
A. 挿入ソート
B. 選択ソート
C. バブルソート
D. マージソート
第9問の解答・解説を見る
正解：A。挿入ソートは既に整列済みなら移動がほぼ不要です。「ほぼ整列済みなら常に他の全方式より速い」とは限りません。交換なしで終了するバブルソートなど、適応的な実装もあります。
第10問
あるソート処理の途中結果が次のようになった。
9, 4, 7, 2
↓4, 7, 2, 9
先頭から末尾へ隣接要素を比較し、逆順なら交換する1巡を行った。この手順を繰り返す方式はどれか。
A. バブルソート
B. 選択ソート
C. 挿入ソート
D. マージソート
第10問の解答・解説を見る
正解：A。指定された隣接交換の手順はバブルソートです。9と4、9と7、9と2を順に交換し、4, 7, 2, 9になります。途中配列だけから実装を一意に断定するのではなく、処理手順も確認します。
間違えた分野から復習する
第1・5・7・10問は途中状態、第2・3・8問は手順、第4・6・9問は計算量と入力条件を確認しましょう。
5種類のソートの仕組みや計算量をまとめて整理するなら、対応するnote教材へ進めます。
コメント