ソートの動きを見るツール

正解：B. 3, 5, 1, 4, 8

5と3を交換して 3, 5, 8, 1, 4、5と8はそのまま、8と1を交換して 3, 5, 1, 8, 4、8と4を交換して 3, 5, 1, 4, 8 になります。1パスで最大値の8が末尾まで運ばれて位置が確定し、次のパスでは残りの4つを同じように並べます。1, 3, 8, 5, 4 は最小値を探して先頭と交換する選択ソートの1パス後の配列、1, 3, 4, 5, 8 はすべて並べ終えた結果です。

正解：A. 10, 13, 14, 37, 29

1回目は全体の最小値10を先頭の29と交換して 10, 29, 14, 37, 13 になります。2回目は2番目以降の最小値13を2番目の29と交換して 10, 13, 14, 37, 29 になります。選択ソートの比較は常に n(n−1)/2 回ですが、交換は1回の操作につき最大1回なので、書き込みの重いデータで有利なことがあります。10, 14, 29, 37, 13 は挿入ソートで2つの要素を差し込んだ後、10, 14, 13, 29, 37 はバブルソートを2パス行った後の配列です。

正解：C. 9回と45回

昇順に並んでいれば、取り出した値は左隣と1回比べるだけで位置が決まるので、9個の要素で合計9回です。降順なら、i 番目に取り出す値は左にある i 個すべてと比べるので、1 + 2 + … + 9 = 45回になります。このように挿入ソートは、最良 O(n)、最悪 O(n²) と入力によって大きく変わり、ほぼ整列済みのデータには非常に速いという特徴があります。この性質を活かし、間隔を空けた要素どうしで先に挿入ソートを行うのがシェルソートで、Timsort なども短い区間に挿入ソートを使います。

正解：B. ヒープソート

ヒープソートは、配列の中に二分ヒープを作り、根の最大値を末尾と交換してヒープを縮めることを繰り返すので、最悪でも O(n log n) で、追加の領域は定数で済みます。マージソートも最悪 O(n log n) ですが、配列で行うには作業用に n に比例する領域が必要です。クイックソートは平均 O(n log n) で実際には速いものの、ピボットの選び方とデータによっては O(n²) になります。なお、ヒープソートは離れた位置の要素を比べるのでキャッシュの効率が悪く、安定でもありません。

正解：A. B, D, A, C

安定ソートでは、キー(ここでは点数)が同じ要素どうしは、並べ替える前の順番がそのまま保たれます。70点の B と D は元の順に B、D、80点の A と C も元の順に A、C となるので、B, D, A, C です。安定なソートにはバブルソート、挿入ソート、マージソートがあり、選択ソート、クイックソート、ヒープソートは一般に安定ではありません。安定ソートを使うと、先に名前順に並べてから点数で並べ直すといった、複数のキーでの並べ替えができます。

正解：C. すでに整列済みのデータで、常に先頭の要素をピボットにする場合

クイックソートは、ピボットより小さい要素と大きい要素に分け、それぞれをさらに分けていきます。整列済みのデータで常に先頭をピボットにすると、毎回ピボットが最小値になり、分割が「0個と残り全部」に偏るため、比較は n(n−1)/2 回(n = 100 なら4,950回)になります。ピボットを無作為に選んだり、3つの値の中央値にしたりすると、偏った分割が続く可能性は非常に小さくなります。データの個数は計算量に関係しません。

正解：B. 7回

1と2、4と2、4と3、4と8、7と8、9と8、9と10を比べ、ここで最初の列が空になるので残りの10は比べずに出力します。比較は7回で、長さ m と n の列をマージするときの最大の回数 m + n − 1 = 7 に当たります。マージは整列済みの列を先頭から1回ずつ見るだけなので O(m + n) で済み、これを log₂ n 段繰り返すのでマージソート全体は O(n log n) になります。