少数の要素を並べ替える場合があります。小規模では、私は3または4を意味します。私はおそらく、このような小さな問題のセットでは、ソート関数を呼び出すのではなく、いくつかのタイプの明示的または直接的なメソッドを使用したいと考えています。 2は簡単ですが、3つの要素は依然としてかなりシンプルですが、4つ以上のアイテムがあり、挿入の並べ替えを簡単に実行できることを好むようになり始めています。少数の要素を並べ替える
inline void sort_n(int *list)をコーディングする利点を期待できる要素はいくつですか？ 4？ 5？ 6？
このトピックでは、sorting int array with only 3 elementsには、3つの要素をソートするための2つのソリューションがあります。もう一方は比較を最小限に抑えますが、より複雑です。スピードのために上に出てくる近代的なアーキテクチャでは？
この最適化を実行する価値があるかどうかを判断するには、まずアプリケーションのプロファイリングを行う必要があります。私はそれがないと思う。標準ライブラリ（またはブースト）関数は、ほぼ確実にソートのための最善の策になります。
あなたはもちろん正しいですし、私は時期尚早に最適化している可能性があります。しかし、私は常に、特定の状況で行うべき最善のことを知りたいと思っています。違いを判断するためにこの道を進む必要があると誰も気付かなければ、正しい答えが実際に役に立たないかもしれないことを知っていると思います。しかし、私はまだ答えを知りたい。 –
カスタムソートを使用すると、デバッグ、保守、理解、または別のプラットフォームへの移植が難しくなります。練習としては面白いことがありますが、手作業でソートすることは特定の狭いケースではより高速になることがよくありますが、正しくコーディングするには時間がかかり過ぎます。 – rkb
プロファイルあなたのアプリケーションはボトルネックになっていますか？または、過度に最適化しようとしていますか？
Bubblesortも非常にうまく動作します。特に、データがすでにソートされている場合、実際には最適であり、テキストブックのマージまたはヒープのソートを上回ります。完全な制約（要素の交換、安定性の要件、その場でのコストなど）を与えない限り、誰もこれに完全に答えることはできません。
とにかく、効率的なマージソートをインラインで実装する方法は、4つの要素では明らかです。
奇数（2の累乗ではない）のサイズの場合、後方挿入の並べ替えは一般的な最適化です。 Javasソートの実装を見てください。私はそれが既にそのような小さな配列の最適化を持っていると信じています。あなたが呼んだソートルーチンがこのような最適化をしていないことを確認しましたか？
私は、挿入ソートは既にソートされたデータのバブルソートより優れていると思います。他の「ナイーブな」アルゴリズムの相対的なメリットについてのあなたの意見は、まだ低いスケールで立っています。 – phs
どちらも 'O（n-1）'の比較とデータの変更を必要とせず、データをトラバースする方向を除いてまったく同じです。 *なぜ、挿入ソートが優れているのでしょうか？ –
インテリジェントなヒープソートのインプリメンテーションでは、カットオフのしきい値が低くなり、それ以降は挿入の並べ替えが使用されるため、基本的にはそこで得られる利点が制限されることを忘れないでください。サイズがコンパイル時にわかっているなら、確かにデフォルトの解決策を打ち負かすことができます。しかし、そのコードは毎秒何百万回も呼ばれる方がいいでしょう。そうでなければ、一握りのサイクルを心配するのは無意味です。 – Voo
標準ライブラリのソートには、小文字の最適化のケースがあると言われます。n - 私はそれを検証しようとしたことはありません。
それは少なくとも、合理的でしょう。ライブラリを書くとき、このような最適化が理にかなっています。私はそれがHaskellのライブラリ[vector-algorithms]（http://hackage.haskell.org/packages/archive/vector-algorithms/0.5.3/doc/html/Data-Vector-Algorithms-Optimal.html）で行われていることを知っています）、 'qsort'や' std :: sort'がそれをしても驚くことはありません。 –
妥当な数の項目については、比較を明示的にコーディングすることによるパフォーマンス上の利点が常に得られます。しかし、非常に少数のアイテムをソートすることは時間がかからず、とにかくどのメソッドを使用するかはまれです。
パフォーマンス上の利点が得られないしきい値は、CPUキャッシュにはそれ以上収まらないほど多くのコードを取得する場合です。したがって、実行しているCPUによってしきい値が異なるところですに。
また、このようなコードのテスト方法も検討する必要があります。あなたが持っているコードが多いほど、バグがないことを確認するのが難しくなります。
通常、小さなデータには挿入ソートとバブルソートが使用されます。
私はこれらの2ウィキペディアの文章を引用し、挿入ソートが好ましいと考えている：
バブル：
クイックソートの実装では、ある一定の閾値
そして、より小さなアレイ用の挿入ソートを使用しますソートは現代のCPUハードウェアとのやり取りも貧弱です。これは、挿入ソートの2倍以上の書き込み、2回のキャッシュミス、および漸近的に多くのブランチ誤予測を必要とします。 JavaのAstrachanソートストリングによる実験では、バブルソートは挿入ソートより約5倍遅く、選択ソートよりも40％遅くなっています。
いつもと同じように、スピードに本当に関心がある場合は、プロファイルする必要があります。
+1 Astrachanを引用してください！ – rkb
最適化に関する質問に対するすべての回答は、プロファイルを作成してボトルネックを最適化する必要があるという警告が付いている必要があります。
C/C++の精神で、私は今すぐを信用し、あなたが尋ねた質問に答えてください。
質問に対する回答は、反復的にプロファイリングすることで決定します。
書き込みtemplate <int N> inline void sort_n(int * list)デフォルトの実装では、標準のlibソートが使用されます。このテンプレートは、コード内で適切なときに使用してください。次に、専門化をまだ行っていない最小のN件のテンプレート特殊化を作成します。このスペシャライゼーションを作成した後、プログラムのプロファイルを作成し、パフォーマンスが大幅に向上したかどうかを確認します。あなたが重要と判断した業績評価を行う場合は、それを繰り返します。専門分野を書いて、それから多くを得ることができなければ、やめてください。
あなたはあなたの手でコード化された一種だったどれだけ速く、測定されましたか？ –
まだコード化されていません。私は、3または4要素のカスタムソートがどれほど非効率であっても、私が必要とするよりも速くなることを知っています。私は何をすべきか知りたいので頼んでいる。それは私が推測するそれの原則についてです。 –
std :: sortよりも（測定可能な）利点を得ることに驚いています（特に、コンパイラが行うことができるすべての最適化の後）。 –