何が安定をソートアルゴリズムはなぜ重要なのでしょうか？

StackOverflow https://stackoverflow.com/questions/1517793

質問

私は非常に興味のある人は、なぜ安定するのではない重要な選別アルゴリズム?

役に立ちましたか？

解決

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

の背景の「安定」ソートアルゴリズムは、順序で同じソートキーで項目を保持します。我々は5文字の単語のリストを持っていると仮定します：

peach
straw
apple
spork

私たちは、各単語の最初の文字だけでリストを並べ替える場合は、安定したソートが生じるであろう。

apple
peach
straw
spork

での不安定なのソートアルゴリズム、strawまたはsporkを入れ替えてもよいが、安定した一つに、彼らは（strawを入力してsporkの前に表示されますので、それは、それを、ある同じ相対位置にとどまりますまた、出力のspork）の前に表示されます。

その後、1、その後、その後、列5、4、3、2、で安定ソート：

私たちは、このアルゴリズムを使用した単語のリストを並べ替えることができます。 最後に、それは正しくソートされます。そのことを自分自身を納得させます。

（ちなみに、そのアルゴリズムは、基数ソートと呼ばれています）

さて、あなたの質問に答えるために、我々は最初と最後の名前のリストがあるとします。私たちは「最初で最後の名前で、」ソートするよう求めています。私たちは、最初の名、姓によって安定したソートで（安定または不安定）並べ替えることができます。これらの種類の後、リストは主に姓でソートされます。姓が同じでどこただし、最初の名前が並べ替えられています。

あなたは同じように不安定な種類をスタックすることはできません。

他のヒント

安定したソートアルゴリズム の種と同一の要素を同じ順序としてそれらの入力も不安定なソート ない場合 を満たす。

安定した選別アルゴリズム

  • 挿入ソート
  • マージソ
  • バブルソート
  • ティム-ソート
  • 計数ソート

不安定なソートアルゴリズム

  • ヒープソート
  • 選択ソート
  • シェルソ
  • クイックソート

enter image description here

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

だから、安定性の問題、および場合のみならば、あなたは解決している問題は、相対的な順序の保持を必要とします。

あなたは安定性を必要としない場合は、

、あなたはヒープソートやクイックソートのように、ライブラリから高速で、メモリ・飲みアルゴリズムを使用して、それを忘れることができます。

あなたは、安定性が必要な場合は、

、それはもっと複雑です。安定したアルゴリズムは、不安定なアルゴリズムよりも高いビッグOのCPUおよび/またはメモリ使用量を持っています。あなたが大規模なデータセットを持っているときに、あなたは、CPUやメモリを叩き間で選択する必要があります。あなたはCPUとメモリの両方に制約している場合は、問題を抱えています。良好な妥協安定したアルゴリズムは、バイナリツリーの一種です。 href="http://en.wikipedia.org/wiki/Binary_tree_sort"はWikipediaの記事をrel="noreferrer">

あなたは、各レコードの最後のインプレースキーとして、元のレコード番号を追加することにより、安定したものに不安定なアルゴリズムを作ることができます。

安定性が重要になることがいくつかの理由があります。一つは、ページがダーティとマークされ、二つのレコードは、それらを交換することにより、スワップする必要がない場合は、メモリ更新を引き起こす可能性があります、ということで、ディスク（または別の遅い培地）に再書き込みする必要があります。

それはあなたが何をするかに依存します。

あなたが最初と最後の名前フィールドで、一部の人の記録を持っている想像してみてください。まず、最初の名前でリストを並べ替えます。あなたが最後の名前で安定したアルゴリズムでリストを並べ替える場合は、姓と名順にソートされたリストを持っています。

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

しかしながら、安定していない任意のソーティングALGOが安定するように改変することができます。そこにそれを安定させるためにアルゴ特定の方法をソートすることができるが、一般に、本質的に安定していない任意の比較基づくソーティングアルゴリズムは、2つのキーの比較のように位置を考慮するようにキー比較動作を変更することによって、安定するように修飾することができます同じキーを持つオブジェクトの因子。

参照： http://www.math.uic.edu /~leon/cs-mcs401-s08/handouts/stability.pdfする http://en.wikipedia.org/wiki/Sorting_algorithm#Stabilityする

ないので多くの答えがこもっており、 この答え, により、 ロバート-ハービー, とにまとめた、いくつかの明:

安定したう一つを犠牲にすることのない確性と客観性を保証するためには、入力の設定は、[安定]アルゴリズムとを区別しない二つ以上の項目です。

源

あなたがソートされているものを想定する場合は、単に数字だけでそれらの値は、/（同じ値を持つなどの要素がidenticleある）それらを区別識別され、

、その後、ソートの安定性の問題が無意味です。

しかしながら、別個であってもよいソーティングに同じ優先度を持つオブジェクト、いつかそれらの相対的順序は、意味のある情報です。この場合、不安定なソートは問題が発生します。

たとえば、あなたは、ゲーム内のレベル[L]で迷路をきれいにするために、すべてのプレイヤーの時間コスト[T]を含むデータのリストを持っています。 我々は、彼らが迷路をきれいにどのように高速で選手をランク付けする必要があるとします。しかし、追加のルールが適用されます。より高いレベルで迷路をきれいプレイヤーは常に時間コストがどのくらいに関係なく、高いランクを持っていません。

もちろん、あなたはルールに従うし、[R]の値を持つすべての選手をランク付けするいくつかのアルゴリズムで実数[R]と対値[T、L]をマップしようとする可能性があります。

安定したソートが可能である場合は、

しかし、あなたは、単に[T]（最初のより速い選手）で全体のリストをソートしてから、[L]であります。あなたは、彼らがきれいに迷路のレベルによってそれらをグループ化した後、この場合、（時間コストによる）選手の相対的な順序は変更されません。

PS：二回ソートするコースのアプローチは、それは十分なはずポスターの問題を説明するが、特定の問題に対する最善の解決策ではありません。

。

安定したソートは常に同じ入力に同じ溶液（順列）を返します。

例えば、[2,1,2]は順列として安定したソートを使用してソートする[2,1,3]（最初のソート出力インデックス2、次いで、インデックス1、インデックス3である）出力を常にシャッフルされることを意味つまり同じ方法。他の非安定したが、それでも正しい順列がある[2,3,1]。

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

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top