JS データ構造とアルゴリズム_ソートおよび検索アルゴリズム

序文

これは「JavaScript のデータ構造とアルゴリズムを学ぶ」の最後のブログです。これは、面接でよく聞かれる内容の一部であるソートと検索でもあります。このブログ投稿の前は、ソートの問題を見ると、バブル ソート、2 層トラバーサル、それだけだと思い込んでいて、ソート関連の問題を詳しく調べようとは思っていませんでした。同じような経験をお持ちの方は、以下の内容が参考になれば幸いです。

1. 準備

本題に入る前に、いくつかの基本的な機能を準備しましょう

（１）配列の２つの要素を入れ替える

関数 swap(arr, ソースインデックス, ターゲットインデックス) {  
  temp = arr [ソースインデックス]とします。  
  arr[ソースインデックス] = arr[ターゲットインデックス];  
  arr[ターゲットインデックス] = temp;  
 }

（２）0～Nの配列を素早く生成します。その他の生成方法については、こちらをクリックしてください。

関数createArr(長さ) {  
  Array.from({length}, (_, i) = > i);を返します。  
 }

（３）シャッフル機能

シャッフル機能を使用すると、配列をすばやくシャッフルできます。一般的な用途としては、音楽の再生順序を切り替えることが挙げられます。

関数シャッフル(arr) {  
  （ i = 0とすると、i <   arr.長さ; i += 1) {  
    const rand = Math.floor (Math.random() * (i + 1));  
    （ランド！== i）の場合{  
      スワップ(arr, i, rand);  
    }  
  }  
  arr を返します。  
 }

2. ソート

一般的なソートアルゴリズムは、次の 2 つのカテゴリに分けられます。

• 比較ソート: 比較によって要素の相対的な順序を決定します。時間計算量は O(nlogn) を超えることができないため、非線形時間比較ソートとも呼ばれます。
• 非比較ソート：比較によって要素の相対的な順序を決定しません。比較ソートに基づく時間下限を突破し、線形時間で実行できるため、線形時間非比較ソートとも呼ばれます。

このブログでは、比較ソートのいくつかのソート方法のみを紹介します。

2.1 バブルソート

バブルソートはすべてのソートアルゴリズムの中で最も単純なもので、通常はソートを学習するための入門書となります。しかし、実行時間の観点から見ると、バブルソートは最悪のソート方法です。

コア: 隣接する 2 つの項目を比較し、最初の項目が 2 番目の項目より大きい場合はそれらを交換します。泡が表面に上がってくるように、アイテムは正しい順序で上方に移動するので、バブルソートと呼ばれます。

注: 最初のレイヤーを走査して残りの要素の最後の値を見つけ、最後の値を指定された位置まで順番にバブルアップします。

コード：

関数 bubbleSort(arr) {  
  const len ​​= arr .length;  
  （ i = 0とすると、i <  長さ; i += 1) {  
    （ j = 0とすると、j <  長さ- 1 - i; j += 1) {  
      if (arr[j] > arr[j + 1]) { // 隣接する要素を比較する 
        スワップ(arr, j, j + 1);  
      }  
    }  
  }  
  arr を返します。  
 }

2.2 選択ソート

選択ソートは、インプレース比較ソート アルゴリズムです。

コア: まず、ソートされていないシーケンス内の最小要素を見つけて、ソートされたシーケンスの開始位置に格納します。次に、残りのソートされていない要素から最小要素を探し続け、ソートされたシーケンスの最後に配置します。すべての要素がソートされるまでこれを繰り返します。

注: 最初のレイヤーは、残りの要素の最小値のインデックスを見つけるためにトラバースし、現在の位置と最小インデックス値を交換します[順番に最小値を見つけます]

コード：

関数selectionSort(arr) {  
  const len ​​= arr .length;  
  minIndexを設定します。  
  （ i = 0とすると、i <  長さ- 1; i += 1) {  
最小インデックス= i;  
    （ j = i + 1とすると、j <  長さ; j += 1) {  
      （arr[minIndex] > arr[j]）の場合{  
 minIndex = j ; // 最小値に対応するインデックスを見つける 
      }  
    }  
    minIndex === iの場合、続行します。  
    swap(arr, minIndex, i);  
  }  
  arr を返します。  
 }

2.3 挿入ソート

挿入ソートの比較順序は、バブルソートや選択ソートと異なります。挿入ソートの比較順序は、現在の項目を前方に比較することです。

コア：順序付けられたシーケンスを構築することで、ソートされていないデータの場合は、ソートされたシーケンスの後ろから前に向かってスキャンし、対応する位置を見つけて挿入します。

注: 2番目の項目から始めて、現在の項目の前のシーケンスが順番に配置されていることを確認するために、順方向に比較します。

コード：

関数挿入ソート(arr) {  
  const len ​​= arr .length;  
  現在のポインタを渡す;  
  （ i = 1とすると、i <  長さ; i += 1) {  
現在の= arr [i];  
ポインタ= i;  
    while(ポインタ> = 0 && 現在の値<   arr [ポインタ - 1]) { // 毎回前方比較する 
      arr[pointer] = arr[pointer - 1]; // 前の項目がポインタ項目より大きい場合は、1項目分前進する 
      ポインタ- = 1 ;  
    }  
    arr[pointer] = current; // ポインタ項目は現在の項目に復元されます 
  }  
  arr を返します。  
 }

2.4 マージソート

マージソートとクイックソートは、上記の3つのソートアルゴリズムよりも実際にはより実現可能です（第4セクションでは、これらのソートアルゴリズムを実際の複雑さに基づいて比較します）。

JavaScript Array クラスは、JavaScript 配列をソートするためのソート関数 (Array.prototype.sort) を定義します。 ECMAScript ではどのソートアルゴリズムを使用するかは定義されていないため、ブラウザメーカーが独自にアルゴリズムを実装できます。たとえば、Mozilla Firefox は Array.prototype.sort の実装としてマージソートを使用しますが、Chrome はクイックソートのバリアントを使用します。

マージソートは分割統治アルゴリズムです。アイデアは、元の配列を、各小さな配列に位置が 1 つだけになるまで小さな配列に分割し、その後、小さな配列を大きな配列にマージして、ソートされた大きな配列が 1 つだけになるまで続けることです。したがって再帰が必要である

コア: マージソート、2つの配列に分割し、別々にソートしてからマージする

注: 再帰内の最小の左と右の配列は、単一要素の配列と比較されるため、上位レベルで複数の要素を比較する場合は、左と右の配列が順序どおりになっている必要があります。

コード：

関数 mergeSort(arr) {  
  const len ​​= arr .length;  
  長さ<   2 ) return arr; // 再帰終了条件 
  const middle = Math .floor(len / 2); // 左と右の配列を分割する 
  const left = arr .slice(0, middle);  
  const right = arr .slice(middle);  
  merge(mergeSort(left), mergeSort(right)) を返します。  
 }  
 function merge(left, right) { // 左側と右側を比較してマージする 
  定数ret = [];  
  (左の長さ && 右の長さ) {  
    （左[0] >右[0]）の場合{  
      ret.push(右シフト());  
    } それ以外 {  
      ret.push(左にシフト());  
    }  
  }  
  while (左.長さ) {  
    ret.push(左にシフト());  
  }  
  while (右.長さ) {  
    ret.push(右シフト());  
  }  
  ret を返します。  
 }

2.5 クイックソート

クイックソートはおそらく最も一般的に使用されるソートアルゴリズムです。その複雑度は O(nlogn) であり、そのパフォーマンスは通常、複雑度が O(nlogn) の他のソート アルゴリズムよりも優れています。マージソートと同様に、クイックソートも分割統治法を使用して元の配列を小さな配列に分割します。

コア：分割統治アルゴリズム、基準値を境界としてそれより小さい値と大きい値を分離する

注: 各トラバーサルはベンチマークポイントより小さい値を除外します

コード：

関数 quickSort(arr, left = 0 , right = arr .length - 1) {  
  // 左と右はデフォルトで配列の最初と最後になります 
  （左<  右） {  
    パーティションを作成します。partitionIndex = partion(arr, left, right);  
    クイックソート(arr, 左, パーティションインデックス - 1);  
    クイックソート(arr、パーティションインデックス+1、右);  
  }  
  arr を返します。  
 }  
関数パーティション(arr, left, right) {  
  pivotをleft とします。  
  let index = left + 1; // 比較条件を満たす項目は分割点の後に配置されます 
  ( i =インデックス、i < = 右、i += 1 とします) {  
    もし(arr[i] <   arr [ピボット]) {  
      swap(arr, i, インデックス);  
      インデックス += 1;  
    }  
  }  
  swap(arr, index - 1, pivot); // 順序を入れ替える場合は、区切り文字を最後の桁に置き換えます 
  インデックス - 1 を返します。  
 }

3. 検索アルゴリズム

3.1 シーケンシャルサーチ

順次検索または線形検索は、最も基本的な検索アルゴリズムです。そのメカニズムは、データ構造内の各要素と探している要素を比較することです。順次検索は最も効率的な検索アルゴリズムです。

関数 findItem(item, arr) {  
  （ i = 0とすると、i <   arr.長さ; i += 1) {  
    if (項目=== arr[i] ) {  
      i を返します。  
    }  
  }  
  -1 を返します。  
 }

3.2 二分探索

バイナリ検索では、検索対象のデータ構造がすでにソートされている必要があります。アルゴリズムが実行する手順は次のとおりです。

1. 配列の中央の値を選択する
2. 選択された値が検索対象の値である場合、アルゴリズムが実行される。
3. 検索する値が選択した値より小さい場合は、手順 1 に戻り、選択した値の左側のサブ配列を検索します。
4. 検索する値が選択した値より大きい場合は、手順 1 に戻り、選択した値の右側のサブ配列を検索します。

関数binarySearch(item, arr) {  
 arr = quickSort (arr); // ソート 
  low = 0とします。  
  high = arr .length - 1 とします。  
  ミッドにします。  
  (低< = 高) {  
 min = Math.floor ((low + high) / 2);  
    もし（arr[mid] <  アイテム） {  
低=中+ 1;  
    } そうでなければ (arr[mid] >項目) {  
高=中- 1;  
    } それ以外 {  
      ミッドに戻ります。  
    }  
  }  
  -1 を返します。  
 }

4. アルゴリズムの複雑さ

4.1 Big O 表記法の理解

Big O 表記法は、アルゴリズムのパフォーマンスと複雑さを記述するために使用されます。アルゴリズムを分析するときに、次のタイプの関数に遭遇することがよくあります。

(1) O(1)

関数の増分(数値){  
    ++num を返します。  
 }

実行時間とパラメータは無関係です。したがって、上記の関数の計算量はO(1)（定数）である。

（２）O(n)

順次検索機能を例にとると、要素を見つけるには、要素が見つかって停止するまで配列全体を走査する必要があります。関数を実行するための総コストは、配列要素の数 (配列のサイズ) と検索対象の値によって異なります。ただし、関数の複雑さは最悪のケースによって異なります。配列のサイズが 10 の場合、オーバーヘッドは 10 です。配列のサイズが 1000 の場合、オーバーヘッドは 1000 です。この関数の時間計算量は O(n) です。ここで、n は (入力) 配列のサイズです。

（３）O(n2)

バブルソートを例にとると、最適化されていない場合、各ソートは n*n 回実行する必要があります。時間計算量はO(n2)である。

時間計算量が O(n) のコードにはループの層が 1 つしかありませんが、時間計算量が O(n2) のコードにはネストされたループの層が 2 つあります。アルゴリズムに配列を走査する 3 つのネストされたループがある場合、その時間計算量は O(n3) になる可能性があります。

4.2 時間計算量の比較

（１）一般的なデータ構造の時間計算量

（２）ソートアルゴリズムの時間計算量