安定ソートとは

あんていそーと

キーが同じ要素どうしの順番が、並べ替えた後も元のまま保たれるソート。バブルソート、挿入ソート、マージソートは安定で、選択ソート、クイックソート、ヒープソートは一般に安定ではない。複数のキーで順に並べ替えるときに必要になる。

「安定ソート」は、1分野の1問の練習問題に出てきます(データ構造とアルゴリズムなど)。

この用語の分野: データ構造とアルゴリズム

安定ソートの練習問題に挑戦

(名前, 点数) のデータ (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 です。安定なソートにはバブルソート、挿入ソート、マージソートがあり、選択ソート、クイックソート、ヒープソートは一般に安定ではありません。安定ソートを使うと、先に名前順に並べてから点数で並べ直すといった、複数のキーでの並べ替えができます。