C ++のクイックソートが遅い

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

  •  05-07-2019
  •  | 
  •  

質問

私は行列の形式で9つの値を持ち、シミュレーションプロセスの一部としてこれらの値から中央値を計算する必要があります。

私はC ++でクイックソートを使用します（つまり、qsort（））。これにより、プロセスの実行が遅くなります（このプロセスが数回繰り返されるため）。

使用できるより良いソートアルゴリズムはありますか？

役に立ちましたか？

解決

中央値を取得するソートは非常に非効率的です。代わりにSTL nth_elementを使用できます：

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

注：nth_elementはベクター/配列を変更しますv。オリジナルを保存する必要がある場合は、最初にコピーを作成します。

他のヒント

マゾヒスト以外のバブルソートは絶対にお勧めしないでください！

小さな値の場合、挿入ソートが最適であり、他のアプリケーションにも適しています（任意の長さのほぼソートされたデータ）。

編集：書式設定をクリーンアップし、提案された回答を強調しました。

9つの値のみ？クイックソートはやり過ぎです。

より小さなデータセットを操作する場合は、おそらく挿入ソート、バブルソート、またはその他の単純なソートアルゴリズムを使用してください。

パフォーマンス

バブルソートには、最悪のケースと平均の複雑さの両方があります。 O（n log n）の非常に優れたワーストケースまたは平均の複雑さを持つ多くのソートアルゴリズムが存在します。挿入ソートなどの他の＆＃1054;（n＆＃178;）ソートアルゴリズムでも、バブルソートよりもパフォーマンスが向上する傾向があります。したがって、nが大きい場合、バブルソートは実用的なソートアルゴリズムではありません。

ただし、当然のことながら、他の人が提案したように、中央値を取得するためにソートする必要さえありませんでした。

  1. ワンバイが述べたように、中央値を得るために完全にソートする必要はありません。

  2. STLには、通常比較インライン化を実行できる sort アルゴリズムがあります。また、qsortが保証するよりもスマートなアルゴリズムを持ち、O（NlgN）の worstcase があります。

quicksortを9個の値のみに使用すると、かなり非効率になります。サンプルサイズが小さい場合は、選択ソートまたは置換ソートを使用する方がはるかに優れています。これらのソート方法ではオーバーヘッドがほとんどありません。

サンプルサイズがしきい値（おそらく50以上）に達すると、QuicksortとMergesortが本当に輝きます。

これらの状況では、組み込み関数を使用するのではなく、独自のコードを作成します。

ほとんどの場合、std :: sort（）アルゴリズムはqsort（）よりも望ましいです。通常は使いやすく、高速に実行されます。

詳細を知りたい場合は、実際には一連のソートアルゴリズムがあります。 Stroustrupは、 The C ++ Programming Language で、std :: sortは使用するのが正確ではないことが多いと書いています。この場合、std :: nth_element（）はおそらくあなたが望むものです。

Quicksortを使用するのに十分な値がないため、高度なアルゴリズムを使用しないでください（例：バブルソート、挿入ソート、... 説明はこちら。

Quicksortのセットアップにはコストがかかり、十分な値がない場合、この獣を使用しても無駄です。

挿入ソート..

小さなデータセットでは、さまざまなアルゴリズムを使用して最適なパフォーマンスを得ることができます。データセットが大きくなると、QuickSortが光ります。

さまざまなアプローチがあります。挿入時に並べ替えるデータ構造を使用できます。また、データセット全体を並べ替える場合もあります。最適なアルゴリズムを見つける必要があります。

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