データ構造とアルゴリズム
(名前, 点数) のデータ (A, 80)、(B, 70)、(C, 80)、(D, 70) がこの順に並んでいる。点数の昇順に安定ソートで並べ替えたときの名前の順はどれか。
- AB, D, A, C
- BD, B, A, C
- CB, D, C, A
答えと解説を見る
正解：A. B, D, A, C
安定ソートでは、キー(ここでは点数)が同じ要素どうしは、並べ替える前の順番がそのまま保たれます。70点の B と D は元の順に B、D、80点の A と C も元の順に A、C となるので、B, D, A, C です。安定なソートにはバブルソート、挿入ソート、マージソートがあり、選択ソート、クイックソート、ヒープソートは一般に安定ではありません。安定ソートを使うと、先に名前順に並べてから点数で並べ直すといった、複数のキーでの並べ替えができます。
- A. 正しい。同じ点数どうしでは元の順(B→D、A→C)が保たれます。
- B. 70点どうしの B と D の順が元と逆になっています。
- C. 80点どうしの A と C の順が元と逆になっています。