この記事は、JavaScriptのソートアルゴリズムをカバーするシリーズの一部です。 あなたはここでシリーズの残りの部分を見つけることができます。 ソートアルゴリズム、または一般的なアルゴリズムに慣れていない場合は、最初にこれを読んで、前進するための強固な基盤を得てください。 今日、私は挿入ソートのインとアウトをカバーすることになります。 挿入ソートはより複雑ですが、バブルソートよりも少し便利です。 最悪のシナリオはbubble sortに似ていますが、その最良のケースは、リストがほぼソートされているか、すでにソートされている可能性が高いと確信している時 のは、全体像を取得してみましょう。
挿入ソートは、リスト内の各要素（2番目の要素から始まる）を見て、それを前の項目と比較することによって機能します。 前の項目が大きい場合は、それらが交換されます。 これは、項目が小さくなるまで続き、その時点でリスト内の次の要素に対して同じことを行います。
挿入ソートはそんなに悪いわけではありません。. 限り、あなたは右の状況でそれを使用するように。
- 小さなリストのほとんどのO(n log n)ソートアルゴリズムよりも高速です。
- 移動されている単一のアイテムにO（1）補助スペースのみを必要とする非常にメモリ効率が高いです。
- それは安定しています—等しい要素はソートされたリストで同じ順序で表示されます。
- それは適応的です—主にソートされたリストをソートするとき、またはすでにソートされたリストに項目を追加するときに高速です。
- 実装は非常に簡単です！
複雑さ
このアルゴリズムの時間複雑さは、最悪の場合、二次—O（n2）です。 Nが無限大に近づくにつれて、平均の場合は最悪の場合に近づきます。 しかし、あなたのリストがソートされているか、またはそれに近い場合、それは最良のケースのシナリオではO（n）になる可能性があるので、そのシナリオに
高速なとき
上記のように、特定の状況下で高速になることがあります。 Merge sortのようなアルゴリズムを使用する場合、すべての項目を分割してからマージする必要があります。 挿入ソートでは、それが正しい「これまでにソートされた」順序であることを確認するだけで、それらすべてを1つのインデックスにシフトします。
挿入ソートは適応ソートであるため、”オンラインアルゴリズム”にもなります。
擬似コード
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
コード
次は? ソートをマージします。 今日のブラウザで最も広く使用されているソートアルゴリズムの一つ。
