387

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

4

10 に答える 10

489

ソート アルゴリズムは、同じキーを持つ 2 つのオブジェクトが、ソート対象の入力配列に表示される順序と同じ順序でソートされた出力に表示される場合、安定していると言われます。挿入ソート、マージ ソート、バブル ソートなど、本質的に安定しているソート アルゴリズムもあります。また、ヒープ ソート、クイック ソートなど、安定していないソート アルゴリズムもあります。

背景: 「安定した」ソート アルゴリズムは、同じソート キーを持つアイテムを順番に保持します。5 文字の単語のリストがあるとします。

peach
straw
apple
spork

リストを各単語の最初の文字だけでソートすると、安定ソートは次のようになります。

apple
peach
straw
spork

不安定な並べ替えアルゴリズムでは、strawまたは交換される可能性がありますが、spork安定した並べ替えアルゴリズムでは、同じ相対位置にとどまります (つまり、入力で前に表示されるため、出力でも前に表示strawされます)。sporkspork

このアルゴリズムを使用して、単語のリストを並べ替えることができます: 5 列目、4 列目、3 列目、2 列目、1 列目の安定した並べ替え。最終的には正しく並べ替えられます。それを自分に納得させてください。(ちなみに、そのアルゴリズムは基数ソートと呼ばれます)

あなたの質問に答えるために、姓と名のリストがあるとします。「姓、次に名」でソートするよう求められます。最初に名で (安定または不安定) を並べ替え、次に姓で安定に並べ替えることができます。これらの並べ替えの後、リストは主に姓で並べ替えられます。ただし、姓が同じ場合は、名がソートされます。

不安定なソートを同じ方法でスタックすることはできません。

于 2009-10-05T00:50:18.377 に答える
28

ソートの安定性とは、同じキーを持つレコードがソートの前後で相対的な順序を保持することを意味します。

したがって、解決しようとしている問題がその相対的な順序の保持を必要とする場合にのみ、安定性が重要になります。

安定性が必要ない場合は、ライブラリから高速でメモリを消費するアルゴリズム (ヒープソートやクイックソートなど) を使用して、それを忘れることができます。

安定性が必要な場合は、より複雑になります。安定したアルゴリズムは、不安定なアルゴリズムよりも Big-O CPU やメモリの使用率が高くなります。したがって、大規模なデータ セットがある場合は、CPU とメモリのどちらを使用するかを選択する必要があります。CPU とメモリの両方に制約がある場合は、問題があります。良い妥協の安定したアルゴリズムは、二分木ソートです。ウィキペディアの記事には、STL に基づく哀れなほど簡単な C++ 実装があります。

元のレコード番号を各レコードの最後のキーとして追加することで、不安定なアルゴリズムを安定したアルゴリズムにすることができます。

于 2009-10-05T01:47:37.710 に答える
21

それはあなたが何をするかによります。

名と姓のフィールドを持つ人のレコードがあるとします。まず、リストを名でソートします。次に、安定したアルゴリズムを使用してリストを姓で並べ替えると、名と姓で並べ替えられたリストが作成されます。

于 2009-10-05T00:47:36.417 に答える
16

安定性が重要である理由はいくつかあります。1 つは、2 つのレコードをスワップしてスワップする必要がない場合、メモリの更新を引き起こす可能性があり、ページがダーティとマークされ、ディスク (または別の低速メディア) に再書き込みする必要があることです。

于 2009-10-05T00:47:10.807 に答える
4

並べ替えアルゴリズムは、同じキーを持つ 2 つのオブジェクトが、並べ替えられていない入力配列に表示される順序と同じ順序で並べ替えられた出力に表示される場合、安定していると言われます。挿入ソート、マージ ソート、バブル ソートなど、本質的に安定しているソート アルゴリズムもあります。また、ヒープ ソート、クイック ソートなど、安定していないソート アルゴリズムもあります。

ただし、安定していない特定のソートアルゴリズムは、安定するように変更できます。アルゴリズムを安定させるためのソートアルゴリズム固有の方法がありますが、一般に、本質的に安定していない比較ベースのソートアルゴリズムは、キー比較操作を変更して安定するように変更し、2 つのキーの比較で位置を等しいキーを持つオブジェクトの係数。

参考文献: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

于 2016-11-07T07:25:55.000 に答える
0

安定した並べ替えは、同じ入力に対して常に同じ解 (順列) を返します。

たとえば、[2,1,2] は順列 [2,1,3] としてステーブル ソートを使用してソートされます (ソートされた出力では、最初にインデックス 2、次にインデックス 1、次にインデックス 3)。つまり、出力は常に同じようにシャッフルされます。その他の安定していませんが、正しい順列は [2,3,1] です。

クイック ソートは安定したソートではなく、同じ要素間の順列の違いは、ピボットを選択するアルゴリズムに依存します。一部の実装はランダムにピックアップし、同じアルゴリズムを使用して同じ入力に対して異なる順列を生成するクイックソートを行うことができます。

安定ソートアルゴリズムは決定論的である必要があります。

于 2009-10-05T00:49:52.560 に答える