JavaScriptで挿入ソートを実装する

Sep29,2016·2分読み取り

この記事は、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

コード

次は? ソートをマージします。 今日のブラウザで最も広く使用されているソートアルゴリズムの一つ。

コメントを残す

メールアドレスが公開されることはありません。