algorithm - さまざまな並べ替えアルゴリズムの「安定」と「不安定」の意味は何ですか？

Question

誰かがさまざまな並べ替えアルゴリズムに関連して「安定」と「不安定」が何を意味するかを説明できますか>アルゴリズムが安定しているかどうか、および不安定な並べ替えアルゴリズムが通常持っているアプリケーション（不安定であるため）をどのように判断できますか？

Answer 1

並べ替えアルゴリズムが「不安定」であると言われる場合、これは、同じランクのアイテムについて、そのコレクションの連続する並べ替えでタイのメンバーの順序が同じままであることが保証されないことを意味します。「安定した」ソートの場合、タイされたエントリは、ソート時に常に同じ順序になります。

アプリケーションの例では、クイックソートアルゴリズムは安定していません。これは、優先度でアクションを並べ替えるような場合にうまく機能します（2つのアクションの優先度が等しい場合、タイのどの要素が最初に実行されるかを気にする必要はありません）。

一方、安定した並べ替えアルゴリズムは、オンラインゲームのリーダーボードなどに適しています。不安定な並べ替え（たとえば、ポイントによる並べ替え）を使用する場合、並べ替えられた結果をWebページで表示しているユーザーは、ページの更新時に異なる結果を経験する可能性があり、結果のページングなどの操作は正しく機能しません。

Answer 2

安定ソートは、同一アイテムの順序を保持します。キーに行インデックスを追加することで、どのような並べ替えも安定させることができます。たとえば、ヒープソートやクイックソートなどの不安定なソートには、本質的にこのプロパティはありませんが、安定したソートよりも高速でコーディングが簡単な傾向があるため、これらが使用されます。私の知る限り、不安定なソートを使用する理由は他にありません。