C++ で double 型の数値を含む配列をソートする最速の方法は何ですか? 最初の長さ 20 と 2 番目の長さ 5000 の 2 種類の配列がありますが、配列の長さによってどのアルゴリズムが最も高速かが異なりますか? 長さ 5000 の配列には、平均で 28 の異なる値が含まれます。
http://www.codeproject.com/Articles/38381/STL-Sort-Comparison-Function
質問する
4343 次
3 に答える
2
最初の質問について: 配列に一意の値のセットが少ない場合 (あなたが言うように 28 のように)、ある種のカウント ソート (フレーバー: 基数、ピジョンホール、バケット) を検討することをお勧めします。配列コンテンツの厳密な制限と範囲を知っていれば、何か良いことができるかもしれません。
しかし、前に述べたように、ソートする要素が 5000 個の配列が大量にない限り、このような小さな配列の場合はおそらく std::sort が適しています。
2 番目の質問: 長さの問題 (空の回答を参照)。O(n log n) は、通常のソートで実行できる最高のものです。通常、O(n^2) は最悪のケースです。O(n^2) は、最悪の場合、20 要素の配列が 20^2 (=400) 操作に対応する時間を必要とし、5000 配列時間が 5000^2 (=2500 万) 操作に対応することを意味します。ご覧のとおり、この場合、より大きな配列はより多くの時間を意味します。あなたのケースと O(n log n) アルゴリズムの場合、5000 配列には 5000 log 5000 (=18500) 操作に対応する時間が必要です。
操作とは何か、それにかかる時間は特定の実装に依存し、一般に比較には関係ありません (したがって、Ordo 記法では無視されます)。配列サイズが十分に大きい場合、O(n log n) アルゴリズムの遅い実装は、O(n^2) アルゴリズムの高速な実装よりも高速です。しかし、20 個の要素のような小さな配列の場合、オーバーヘッドの少ない優れた実装が最も重要です。400 回の高速操作は、26 回の低速操作よりも高速になります。5000 配列の同じ比較では、2500 万回の高速操作は 18500 回の低速操作よりも高速ではないことがわかります。
もう 1 つの要因は、配列の内容です。挿入ソートなどの一部のアルゴリズムは、ほぼ正しい順序の配列では特に高速 (O(n) に近づく) ですが、ランダムな入力では O(n^2) が不十分です。
事前定義された (既知の) 配列コンテンツの制限/範囲 (したがって、通常の並べ替えとして分類されない) を利用することで、並べ替えのカウントは O(n) に近づくことができます。つまり、時間は要素の数に正比例します。ウィキペディアを参照してください。
ハッピーリサーチ！
于 2013-03-17T17:36:23.377 に答える
1
私は違いを生みますが、最善の策はstd::sortを使用することです。入力サイズに応じて、最適と思われるソートアルゴリズムを内部的に切り替えます。
ウィキペディアのリファレンスを参照してください。
于 2013-03-17T15:44:28.700 に答える
1
クイックソート、マージソート、挿入ソート、バブルソートなどのソートアルゴリズムを検索することをお勧めします。
並べ替えは、並べ替えアルゴリズムの表記「ビッグO表記」からわかるように、並べ替えるアイテムの数に大きく依存します。多くの場合、異なる値とデータ型の平均数は、実行時に問題になるほどの違いはありません。（バブルソート）のアルゴリズムはO(n^2)、要素数の2乗の複雑さを持っており、ソートするアイテムの数に関して、時間はほぼ2乗で増加することを示しています。クイックソートはO(n log n)複雑で、最速のソート方法の1つです。
バブルソートは、実装が最も簡単で、実行時に最も時間がかかります。
編集：コメントが言うように、5000の値だけの短い配列は、Bogosortのようなものでなければ、どのアルゴリズムを使用しても実際には大きな違いはありません。
于 2013-03-17T15:47:12.793 に答える