1

入力に基づいてソートアルゴリズムを選択する方法を知りたいと思っていたので、最高の効率を得ることができました。

入力のサイズ、入力の配置方法（昇順/降順）、または使用されるデータ構造などに依存する必要がありますか...？

4

4 に答える 4

4

アルゴリズムの一般的な重要性、およびアルゴリズムの並べ替えにおける重要性は次のとおりです。

(*)正しさ - これが最も重要なことです。アルゴリズムが非常に高速で効率的であっても、それが間違っていれば、何の価値もありません。並べ替えでは、正しく並べ替える候補が 2 つある場合でも、安定した並べ替えが必要です。効率が悪くても安定した並べ替えアルゴリズムを選択します。これは目的に適しているため、もう一方は正しくないためです。

次は基本的に、実行時間、必要なスペース、および実装時間の間のトレードオフです (ライブラリを使用するのではなく、最初から何かを実装する必要がある場合は、わずかなパフォーマンスの向上のために、おそらく価値がありません)。

上記のトレードオフについて考える際に考慮すべき点がいくつかあります。

  1. 入力のサイズ(例: 小さい入力の場合、挿入ソートはより高度なアルゴリズムよりも経験的に高速ですが、 がかかりますO(n^2))。
  2. 入力の場所(ディスク上のソート アルゴリズムは、RAM 上のアルゴリズムとは異なります。ディスクの読み取りは、シーケンシャルでない場合は効率が大幅に低下するためです。通常、ディスク上のソートに使用されるアルゴリズムは、マージ ソートの一種です)。
  3. データはどのように配布されますか? データが「ほぼソート済み」である可能性が高い場合 - 通常ひどいバブル ソートでも、2 ～ 3 回の繰り返しでデータをソートでき、他のアルゴリズムと比較して超高速になる可能性があります。
  4. すでに実装しているライブラリは何ですか? 新しいものを実装するには、どれくらいの作業が必要ですか? それだけの価値はありますか？
  5. 入力のタイプ（および範囲） -列挙可能なデータ（整数など）の場合 - 整数設計アルゴリズム（基数ソートなど）は、一般的なケースのアルゴリズムよりも効率的かもしれません。
  6. 遅延要件- ミサイル ヘッドを設計していて、結果が特定の時間内に返さなければならない場合、最悪の場合には 2 次実行時間に減衰する可能性があるクイックソートは適切な選択ではない可能性があり、別のアルゴリズムを使用することをお勧めします。代わりに厳密なO(nlogn)最悪のケースがあります。
  7. ハードウェア(たとえば、巨大なクラスターと巨大なデータを使用している場合) は、1 台のマシンですべての作業を実行しようとするよりも、分散ソート アルゴリズムの方がおそらく優れています。
于 2012-10-12T15:34:04.850 に答える
3

それはそれらすべてに基づくべきです。

  • 挿入ソートは小さなデータセットなどのクイックソートよりも高速である可能性があるため、データのサイズを考慮する必要があります。

  • アルゴリズムごとにワースト/平均/ベストケースの漸近ランタイムが異なるため、データの配置を知る必要があります（ワースト/平均ケースが同じであるのに対し、ワーストケースと平均が大幅に悪い場合もあります）

  • データがすでに特別な形式になっている場合、またはデータを新しいデータ構造に効率的に入れて自動的に並べ替えを行うことができる場合でも、非常に特殊な並べ替えアルゴリズムがあるため、使用されているデータ構造を知っておく必要があります（ la BSTまたはヒープ）

于 2012-10-12T14:33:00.580 に答える
0

非常に高いレベルで、挿入と各アルゴリズムの比較の比率を考慮する必要があります。

ファイル内の整数の場合、これはそれほど重要ではありませんが、コンテンツに基づいてファイルをソートしている場合は、当然、比較をできるだけ少なくしたいと思うでしょう。

于 2012-10-12T15:07:45.930 に答える
0

ソート アルゴリズムの選択を決定する主な 2 つの要素は、時間の複雑さと空間の複雑さです。シナリオと利用可能なリソース (時間とメモリ) によっては、各並べ替えアルゴリズムが提供するものに基づいて、並べ替えアルゴリズムを選択する必要がある場合があります。

並べ替えアルゴリズムの実際のパフォーマンスは、入力データにも依存します。入力のサイズ、配列が既にどのように並べ替えられているかなど、入力データの特定の特性を事前に知っていると役立ちます。

たとえば、入力データに負でない整数が 1000 個しかないことが事前にわかっている場合、そのcounting sortような配列を線形時間でソートするために非常によく使用できます。

並べ替えアルゴリズムの選択は、空間と時間の制約、および入力データのサイズ/特性によって異なります。

于 2012-10-12T14:35:34.273 に答える