安定なソートと非安定なソートの違いについてのメモ。
安定なソート（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")となる。
非安定なソートの例としては、クイックソート、ヒープソート、選択ソートなどがある。
安定なソートと非安定なソートの違いは、同じキーを持つ要素の相対的な順序が、ソートの前後で保持されるかどうかである。