V8では、10要素を超える長さの配列に対してクイックソートが使用されます。ここでthe sources次のとおりです。V8のArray.sortでのシェルソートに対する挿入ソートの根拠は何ですか？
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
私はシェルソートの代わりに、挿入ソートを使用しないための根拠何思ったんだけど？私はそれがおそらく10要素の配列に違いはないが、まだ理解しています。何か案は？
元の論理的根拠は履歴に失われています。 （短い配列の場合）QuickSortよりも高速であることだけが、短い配列（2008年の終わりまで）のためにInsertionSortを導入したcommitに言及しています。だから、誰かがそれをそのように実装しました。それ以来誰もそれを変更する理由は見当たりませんでした。
短い配列の場合、InsertionSortは非常に効率的であることが知られているので、おそらくそれを変更しても差は出ませんし、チームが実際に差をつけることはたくさんあります。
ありがとうございます。あなたが言っているのは、おそらく誰かが '挿入ソート'を実装していて、それをシェルソートに変更することを検討する理由があったということでしょうか？ –
はい。以前はQuickSortだけでしたが、小さな配列の場合はInsertionSortが追加されていましたが、それ以来、「十分に良い」状態でした。 – jmrk
あなたの助けをたくさんありがとう –
大きな質問です。その根拠は単純ですが、少なくとも典型的には、これらの小さな配列に対して挿入ソートを使用する方が実際には高速です。実際、Javaは長い間、同じスイッチを作っていました。配列の長さがコード内で7未満の場合は、挿入ソートを行います。 hereを参照してください。一番上の関数sort1の下にあります。
このような小さなアレイでは、基本的に（ほとんどの場合）Quicksortのオーバーヘッドが挿入の並べ替えよりも遅くなることがあります。このような場合の挿入ソートは、O（n）で最高のパフォーマンスに近づきやすく、Quicksortは依然としてO（n log n）に留まる可能性が高いです。
一方、シェルソートは挿入ソートよりもはるかに遅くなる傾向があります。それは言われている、それははるかに速く（相対的に）することができます。挿入ソートの最良のケースはまだ0（n）ですが、シェルソートの最良のケースはO（n log n）です。 10歳未満のすべての数は、数学的見地からより速くなる可能性があります。残念ながら、シェルのソートには、より多くのスワップが必要です。シェルの並べ替えは、はるかに遅くなる可能性があります。挿入ソートは、O（1）スワップでスワップすることができる傾向がありますが、シェルのソートはO（n）スワップの周りにある可能性があります。スワップは、スワッピングに3番目の一時レジスタを使用してしまう傾向があるため（XORを使用する方法がありますが、それでもCPU上では通常3つのコマンドです）、コストがかかります。したがって、挿入ソートは通常、実際のマシンで勝ちます。
リンクと情報に感謝しますが、質問はシェルソートと挿入の並べ替えではなく、クイックソートについてです。 –
申し訳ありませんが、私はそれを逃した、これはより良い答えを願っています。 –
明らかに、小さなアレイがそのスイッチを組み込むためにはパフォーマンスの違いが十分にあります。 – Bergi
@Bergi、はい、 '挿入sort'は' quick sort'より小さい配列では良いですが、 'shell sort'は小さな配列の' insertion sort'よりも良いです。 –
Afaikシェルのソートは挿入の並べ替えとあまり変わりません。それが価値ある変更だと思って現実的なベンチマークを書くことができるなら、私はV8チームがパッチについて喜んでいると確信しています。 – Bergi