Javascript
 Computer >> コンピューター >  >> プログラミング >> Javascript

JavaScriptで挿入ソートを実装する方法は？

挿入ソート

配列をソートするのは非常に単純な比較ソートです。 比較ソート 並べ替えようとしている現在の値を配列内の他の値と比較します。一度に1つのアイテムを処理し、必要な並べ替えられた配列を取得するために、各アイテムを正しい場所に繰り返し配置します。

実際、挿入 ソートは、ヒープソートなどの一部の高度なアルゴリズムほど効率的ではありません。 またはマージソート 。大規模なプログラムを扱う場合、これは最良のオプションではありません。 隠れた定数値が低いため 、挿入ソートは、小さな配列を処理する際に、ヒープやクイックソートなどの高度なアルゴリズムの一部よりも優れています。 。

挿入ソート 配列上を左から右に移動することで機能します。 現在のアイテムを使用します 「キー」として そのキーの左側にある値を検索して、キーが実際に存在する場所を見つけます。

アルゴリズム

次の例では、指定された配列は0、-3,5,8,2,7,6

です。
  • 反復0 -最初の反復では、実際のソートされていない配列は0、-3、5、8、2、7、6のみです。
  • 反復1 -この反復では、キーはインデックス1の値-3です。挿入ソートは、キーをそのキーの左側の値と比較し、プロセスを続行します。 -3は0未満であるため、配列を-3,0,5,8,2,7,6として指定することにより、0の左側に移動します。
  • 反復2 -ここでのキーは5（インデックス2の値）です。左側の-3と0の値と比較され、ソートされた値に配置されます。したがって、反復2の後の配列は-3,0,5,8,2,7,6です。
  • 反復3 -この反復では、キー値8が左側の要素と比較され、最終的な配列は-3,0,5,8,2,7,6になります。
  • 反復4 -この反復では、キー値2が左側の値と比較され、ソートされた位置に配置されます。したがって、反復4後の最終的な配列は-3,0,2,5,8,7,6です。

同様に、最後の反復の終了時に、ソートされた配列は-3,0,2,5,6,7,8

になります。

例

<html>
<head>
<script>
   function iSort(array)  {
      for (var p = 1; p < array.length; p++)   {
   if (array[p] < array[0]){
      array.unshift(array.splice(p,1)[0]);
   }
   else if (array[p] > array[p-1]){
      continue;
   }
   else {
      for (var q = 1; q < p; q++) {
         if (array[p] > array[q-1] && array[p] < array[q]){
            array.splice(q,0,array.splice(p,1)[0]);
            }
          }
       }
   }
   return array;
   }
   document.write(iSort([0,-3,5,8,2,7,6]));
</script>
</body>
</html>

出力

-3,0,2,5,6,7,8

  1. JavaScriptのArray.prototype.sort（）。

    JavaScript Array.prototype.sort（）メソッドは、配列の並べ替えに使用されます。並べ替えの順序は、アルファベット、数字、昇順、降順のいずれかです。 以下は、Array.prototype.sort（）メソッドのコードです- 例 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8" /> <meta name="viewport" content="width=device-

  2. 挿入ソート

    この並べ替え手法は、カードの並べ替え手法と似ています。つまり、挿入ソートメカニズムを使用してカードを並べ替えます。この手法では、データセットから1つの要素を取得し、データ要素をシフトして、取得した要素をデータセットに挿入し直す場所を作成します。 挿入ソート手法の複雑さ 時間計算量：最良の場合はO（n）、平均および最悪の場合はO（n ^ 2） スペースの複雑さ：O（1） 入力と出力 Input: The unsorted list: 9 45 23 71 80 55 Output: Array before Sorting: 9 45 23 71 80 55 Array after Sort