algorithm - 安定した効率的なソート？

Question

スペース効率が非常に高い、珍しい連想配列の実装を作成しようとしています。次のすべてを満たす並べ替えアルゴリズムが必要です。

安定（キーが等しい要素の相対的な順序は変更されません。）
インプレースまたはほぼインプレース（O（log n）スタックは問題ありませんが、O（n）スペースの使用またはヒープの割り当てはありません。
O（n log n）時間計算量。

また、並べ替えられるデータ構造は配列であることに注意してください。

これら3つのいずれかに一致する基本的なアルゴリズムがあることは簡単にわかります（挿入ソートは1と2に一致し、マージソートは1と3に一致し、ヒープソートは2と3に一致します）が、私は一生の間、それを見つけることができません。これらの3つの基準すべてに一致します。

score 10 · Accepted Answer

マージソートは、インプレースであると私が信じているように書くことができます。それが最善のルートかもしれません。

score 9 · Accepted Answer

注: 標準のクイックソートはO(n log n)ではありません! 最悪の場合、O(n^2) 時間かかることもあります。問題は、中央値から遠く離れた要素をピボットする可能性があるため、再帰呼び出しが非常に不均衡になることです。

これに対抗する方法があります。それは、中央値に近いことが保証されている、または少なくとも非常に可能性の高い中央値を慎重に選択することです。線形時間で正確な中央値を実際に見つけることができるのは驚くべきことですが、あなたの場合は速度を気にしているように聞こえるので、これはお勧めしません。

最も実用的なアプローチは、安定したクイックソートを実装することだと思います(安定性を維持するのは簡単です) が、各ステップでピボットとして 5 つのランダム値の中央値を使用します。これにより、ソートが遅くなる可能性が非常に低くなり、安定します。

ちなみに、マージソートはインプレースで実行できますが、インプレースと安定の両方を行うのは難しいです。

score 3 · Accepted Answer

クイックソートはどうですか？

Exchangeもそれを行うことができ、あなたの条件ではより「安定」しているかもしれませんが、クイックソートの方が高速です。

score 3 · Accepted Answer

Wikipediaに並べ替えアルゴリズムのリストがあります。これには、実行時間、安定性、および割り当てによる分類が含まれます。

あなたの最善の策は、おそらく効率的な不安定なソートを安定したものに変更することであり、それによって効率が低下します。

score 2 · Accepted Answer

クイックソートは、リンクリストで実行することで安定させることができます。これは、3つのピボットのランダムまたは中央値を選択するのにnのコストがかかりますが、定数は非常に小さくなります（リストトラバーサル）。

リストを分割し、左側のリストが同じ値になるように並べ替えられ、右側のリストが同じ値が正しくなるように並べ替えられるようにすることで、実際の追加コストなしで、並べ替えが暗黙的に安定します。また、これはスワッピングではなく割り当てを処理するため、書き込みが1つしかないため、実際には配列のクイックソートよりも速度がわずかに向上する可能性があると思います。

したがって、結論として、すべてのアイテムをリストし、リストでクイックソートを実行します

score 2 · Accepted Answer

要素は (たとえば、リンクされたリストではなく) 配列内にあるため、元の順序に関する情報を配列インデックス自体で利用できます。インデックスを認識するように並べ替え関数と比較関数を作成することで、これを利用できます。

function cmp( ar, idx1, idx2 )
{
   // first compare elements as usual
   rc = (ar[idx1]<ar[idx2]) ? -1 : ( (ar[idx1]>ar[idx2]) ? 1 : 0 );

   // if the elements are identical, then compare their positions
   if( rc != 0 )
      rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0);

   return rc; 
}

この手法は、ソートが要素のスワップのみを実行する限り、任意のソートを安定させるために使用できます。要素のインデックスは変更されますが、同一の要素の相対的な順序は同じままであるため、並べ替えは堅牢なままです。元のヒープ化は相対的な順序を「破棄」するため、ヒープソートのようなソートではそのままでは機能しませんが、アイデアを他のソートに適応させることはできるかもしれません。

score 2 · Accepted Answer

安定したインプレースマージアルゴリズムのクラスがありますが、それらは複雑で線形であり、O(n) にかなり高い定数が隠されています。詳細については、この記事とその参考文献をご覧ください。

編集: マージフェーズは線形であるため、マージソートは nlog_n です。

score 2 · Accepted Answer

クイックソートは、各レコードにシーケンスフィールドを追加し、ソート前にインデックスに初期化し、それをソートキーの最下位部分として使用するだけで、かなり簡単に安定させることができます。

これは所要時間にわずかに悪影響を及ぼしますが、アルゴリズムの時間の複雑さには影響しません。また、レコードごとに最小限のストレージコストのオーバーヘッドがありますが、非常に多数のレコードを取得するまで問題になることはほとんどありません (より大きなレコードサイズで最小化されます)。

独自の記述を避けるために、このメソッドをCの関数で使用しました。qsort()各レコードには 32 ビット整数が追加され、を呼び出す前に開始シーケンス番号が入力されqsort()ます。

次に、比較関数がキーとシーケンスをチェックし(これにより重複キーがないことが保証されます)、クイックソートが安定したものになります。私が使用していたデータセットでは、本質的に安定したマージソートよりもパフォーマンスが優れていたことを思い出します。

あなたの走行距離は異なる場合がありますので、常に覚えておいてください:測定、推測しないでください!

score 1 · Accepted Answer

ウィキペディアには、必要な種類の並べ替え関数を見つけるのに役立つ並べ替え関数の優れたリストがあります。

たとえば、特定の質問に対処するには、インプレースマージソートが必要なようです。

ただし、ストランドの並べ替えも参照してください。非常に興味深いプロパティがいくつかあります。

score 1 · Accepted Answer

O(n log n) が重要であることを実証できるまでは、あまり心配しないでください。大幅に低い定数の O(n^2) アルゴリズムが見つかった場合は、それを選択してください。

データが非常に制約されている場合、一般的な最悪のシナリオは関係ありません。

要するに、いくつかのテストを実行します。

score 1 · Accepted Answer

安定したインプレースクイックソートと安定したインプレースマージソートを実装しました。マージソートは少し高速で、O(n*log(n)^2) で動作することが保証されていますが、クイックソートでは動作しません。どちらも O(log(n)) スペースを使用します。

score 0 · Accepted Answer

おそらくシェルソート？データ構造のコースを正しく思い出せば、安定している傾向がありますが、ほとんどソートされたデータに対してO（n）を実行しますが、最悪の場合はO（n log ^ 2 n）です。挿入ソートに基づいているので、その場でソートします。

score 0 · Accepted Answer

ちょっとマンネリ気味かもしれませんが、手書きのマージソートが好きです。シンプルで安定していて、行儀が良いです。必要な追加の一時ストレージはだけN*sizeof(int)です。これはそれほど悪くありません。

algorithm - 安定した効率的なソート？

13 に答える 13

Related

Reference