安定なソートと非安定なソートの違い

これはなに

安定なソートと非安定なソートの違いについてのメモ。

安定なソート（Stable Sort）では、同じキーを持つ要素の相対的な順序が、ソートの前後で保持される。

たとえば、(1,"A"), (3,"D"), (2,"B"), (2,"C")をソートしたとき、安定なソートでは(2,"B"), (2,"C")の順序は変わらない。ソート後は(1,"A"), (2,"B"), (2,"C"), (3,"D")となる。

安定なソートの例としては、バブルソート、マージソート、挿入ソートなどがある。

非安定なソート（Unstable Sort）では、同じキーを持つ要素の相対的な順序が、ソートの過程で変わる可能性がある。

たとえば、(1,"A"), (3,"D"), (2,"B"), (2,"C")をソートしたとき、非安定なソートでは(2,"B"), (2,"C")の順序の変わる可能性がある。ソート後は(1,"A"), (2,"C"), (2,"B"), (3,"D")となる。

非安定なソートの例としては、クイックソート、ヒープソート、選択ソートなどがある。

安定なソートと非安定なソートの違いは、同じキーを持つ要素の相対的な順序が、ソートの前後で保持されるかどうかである。