[解決済み】ソートアルゴリズムにおける安定性とは何ですか、なぜそれが重要なのですか？

質問

ソートアルゴリズムにおいて、なぜ安定性が重要なのか、あるいは重要でないのか、非常に興味があります。

どのように解決するのですか？

ソートアルゴリズムは、次のように言われています。 <強い 安定 同じキーを持つ2つのオブジェクトが、ソートされる入力配列に現れるのと同じ順番でソートされた出力に現れる場合。ソートアルゴリズムの中には、挿入ソート、マージソート、バブルソートなどのように、もともと安定なものがあります。また、ヒープソートやクイックソートなど、そうでないソートアルゴリズムもあります。

背景 安定したソートアルゴリズムとは、ソートキーが同じものを順番に並べていくものです。 例えば、5文字の単語のリストがあるとする。

peach
straw
apple
spork

各単語の最初の文字だけでリストをソートすると、stable-sort が生成されます。

apple
peach
straw
spork

で 不安定 ソートアルゴリズムです。 straw または spork は入れ替わるかもしれませんが、安定したものでは同じ相対位置に留まります（つまり straw の前に表示されます。 spork の前に表示されます。 spork を出力します)。

このアルゴリズムを使って単語のリストをソートすることができます：列5で安定的にソートし、次に4、3、2、1。 最終的に、正しくソートされます。 自分で納得してください。(ちなみに、このアルゴリズムは基数ソートと呼ばれています。）

さて、質問に答えるために、姓と名のリストがあるとします。 このとき、姓から順に並べ替えるように言われたとします。 まず姓でソート(安定または不安定)し、次に姓で安定ソートすることができます。 これらのソートの後、リストは主に姓でソートされます。 しかし、姓が同じ場合は、姓でソートされます。

不安定なソートを同じように積み重ねることはできません。