プログラマーに必要ないくつかの一般的なソートおよび検索アルゴリズムの概要

[[434262]]

序文

最近、アルゴリズムの基礎を固めるために、アルゴリズムの本にある基本的なアルゴリズムをもう一度見直しました。フロントエンドエンジニアが知っておくべきソートアルゴリズムと検索アルゴリズムの知識を特にまとめました。理解すべき高度なアルゴリズムはまだたくさんありますが、基礎を固める必要があります。この記事では、次のアルゴリズムの知識を画像とテキストの形で紹介します。読んで何かを得ていただければ幸いです。

バブルソートとその最適化
選択ソート
挿入ソート
マージソート
クイックソート
シーケンシャルサーチ
バイナリ検索

文章

[[434263]]

すべてのフロントエンドエンジニアにとって、最も面倒なのはアルゴリズムの問題だと思いますが、アルゴリズムは多くの場合、人のプログラミング能力を測る非常に重要な指標でもあります。現在、多くの主流のフレームワークとライブラリには、大量のアルゴリズムとデザインパターンが適用されています。自分のランクを上げるには、絶えず「モンスターを倒して」（つまり、アルゴリズムを磨いて）アップグレードし、「最強の王」になるしかありません。

実際、フロントエンド開発はここ数年でますます洗練された開発に傾倒しています。多くのスーパーアプリケーション（TaobaoやWeChatなど）は究極のユーザーエクスペリエンスを追求しています。時間はお金であり、エンジニアは以前と同じように使用できるプログラムを開発しないようにする必要があります。より詳細なテスト（ユニットテスト、パフォーマンステストなどを含む）を実行する必要があることがよくあります。ソートを例に挙げてみましょう。大量のデータをソートする場合、バブルソートを使用すると間違いなく批判されます。バブルソートのパフォーマンスは非常に悪いためです（複雑さはO（n ^ 2））。実際のプロジェクトでは、バブルソートを使用することはほとんどなく、クイックソートやシェルソートを使用することが多いです。ソートアルゴリズムのパフォーマンスに関しては、

「フロントエンドアルゴリズムシリーズ」フロントエンドのコードを60倍高速化する方法

詳細な紹介があります。次に、記事の冒頭で、いくつかの一般的なソートおよび検索アルゴリズムを実装する方法を学びましょう。

1. バブルソートとその最適化

ソートアルゴリズムを学ぶとき、習得するのが最も簡単なのはバブルソートです。これは実装が非常に簡単なためですが、実行パフォーマンスの観点からは最悪です。

バブルソートの考え方は、隣接する 2 つの項目を比較し、前者が後者よりも大きい場合はそれらの位置を交換するというものです。

バブルソートのプロセスとパフォーマンステストをより便利に実証するために、著者はまず、指定された数のランダム配列を動的に生成し、要素の位置シーケンスを生成するメソッドであるいくつかのツールメソッドを記述します。コードは次のとおりです。

 // 指定された数のランダム配列を生成する
const generateArr = (num = 10) => {
  arr = [] とします
(i = 0; i< num; i++)の場合{
    item = Math.floor(Math.random() * (num + 1)) とします。
    arr.push(アイテム)
  }
リターン
} 
 
 // 指定された数の要素のx軸座標を生成する
const generateArrPosX = (n= 10, w = 6, m = 6) => {
  pos = [] とします
( i = 0; i< n; i++ とします) {
    アイテム = (w + m) * i とする
    pos.push(アイテム)
  }
戻り位置
}

上記の 2 つの方法を使用すると、任意の数と配列項目の座標の配列を生成できます。次に、この 2 つの方法を使用します。

バブルソートアルゴリズムの乞食バージョンを直接書いてみましょう。

バブルソート(arr = []) {
    len = arr.lengthとします
(i = 0; i< len; i++)の場合{
 (j = 0; j < len - 1; j++)の場合{
        arr[j] > arr[j+1] の場合
          // 交換する
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
      }
    }
リターン
  }

次に、テストしてみましょう。generateArr メソッドを使用して、60 個の配列項目の配列を生成し、要素の座標を動的に生成します。

 // 座標を生成する
定数 pos = generateArrPosX(60)
 // 60 個の項目の配列を生成する
定数arr = generateArr(60)

コードを実行すると、次のランダムノード構造が生成されます。

ここでは CSS の部分を紹介しません。自分で実装できます。次に、上で書いたバブルソートをテストします。[Sort] をクリックすると、結果は次のようになります。

配列が順番にソートされていることがわかります。コードの実行にかかる時間を測定するために console.time を使用できます。上記の「乞食バージョン」のバブルソートには 0.2890625 ミリ秒かかります。

コードを詳細に分析すると、2 層の for ループソートによって冗長なソートが大量に発生することがわかります。外側のループで実行されたラウンド数を内側のループから減算すると、内側のループでの不要な比較を回避できるため、次のようにコードを最適化します。

 // バブルソートの最適化バージョン
バブルソート(arr = []) {
  len = arr.lengthとします
  // 最適化
(i = 0; i< len; i++)の場合{
 (j = 0; j < len - 1 - i; j++)の場合{
      arr[j] > arr[j+1] の場合
        // 交換する
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
リターン
}

最適化されたバブルソートには 0.279052734375 ミリ秒かかります。これは以前よりわずかに改善されていますが、まだ推奨されるソートアルゴリズムではありません。

2. 選択ソート

選択ソートの考え方は、データ構造内で最小の値を見つけてそれを最初に配置し、次に 2 番目に小さい値を見つけてそれを 2 番目に配置する、というものです。

引き続き前のパターンに従い、次のように 60 個の項目の配列を生成します。

選択ソートコードは次のとおりです。

選択ソート(arr) {
    len = arr.lengthとします。
        インデックス最小
(i = 0; i< len -1; i++)の場合{
      インデックス最小値 = i
 (j = i; j < len; j++)の場合{
        arr[indexMin] > arr[j] の場合
          インデックス最小値 = j
        }
      }
      if(i !== インデックス最小値) {
        [arr[i], arr[indexMin]] = [arr[indexMin], arr[i]]
      }
    }
リターン
}

「並べ替え」をクリックすると、結果は次のようになります。

これは、コードが正常に実行され、ソートを実行できることを示しています。コンソールには 0.13720703125 ミリ秒かかり、これは明らかにバブルソートのパフォーマンスよりも優れています。

3. 挿入ソート

挿入ソートの考え方は、最初の項目がソートされていると仮定して、一度に 1 つの配列項目をソートし、次に 2 番目の項目と比較して 2 番目の項目の位置を決定し、同じ方法を使用して 3 番目の項目の位置を決定し、最後に配列全体を小さいものから大きいものの順にソートするというものです。

コードは次のとおりです。

挿入ソート(arr) {
    len = arr.lengthとします。
        じ、
温度;
 (i = 1; i< len; i++)の場合{
      j = 私
temp = arr[i]
      j > 0 && arr[j-1] > tempの間
        arr[j] = arr[j-1]
        じ --  
      }
      arr[j] =一時;
    }
 }

実行結果は次のとおりです。

コンソールの印刷時間は 0.09912109375 ミリ秒です。

4. マージソート

マージソートアルゴリズムは上記の 3 つよりもパフォーマンスが優れており、実際のプロジェクトで使用できますが、実装は比較的複雑です。

マージソートは分割統治アルゴリズムです。元の配列を小さな配列に分割し、各小さな配列に要素が 1 つだけ含まれるようにしてから、小さな配列を大きな配列にマージし、最後にソートされた大きな配列に変換するという考え方です。

実装プロセスを次の図に示します。

このメソッドを実装するには、マージ関数と再帰関数を用意し、次のようにコードを実装する必要があります。

 // マージソート
マージソートレコード(arr) {
 len = arr.lengthとします
 長さが1の場合
リターン
 }
 mid = Math.floor(len / 2)とします。
左= arr.slice(0, 中央)、
右= arr.slice(mid, len)
 merge(mergeSortRec(左), mergeSortRec(右))を返します
}
 //マージメソッド
マージ(左、右) {
    結果 = []
        l = 0,
        r = 0;
    l <左.長さ && r <右) {
      if(左[l]<右(r)){
        result.push(左[l++])
      }それ以外{
        result.push(右[r++])
      }
    }
    while(l <左.length) {
      result.push(左[l++])
    }
    while(r <右.length) {
      result.push(右[r++])
    }
結果を返す
}

上記のコードの再帰関数は、大きな配列を複数の小さな配列に分割して項目を 1 つだけにし、それらをレイヤーごとに結合して並べ替えます。わからないことがあれば、作者とコミュニケーションをとったり、私が描いたスケッチを使って理解したりすることができます。

5. クイックソート

クイックソートは、よく使用されるソートアルゴリズムです。その複雑度は O(nlog^n) で、他の O(nlog^n) 複雑度よりもパフォーマンスが優れています。また、分割統治法を使用して元の配列を分割します。クイックソートは実装が複雑なため、考え方は次のとおりです。

配列の中央の項目をピボットとして選択する
2 つのポインタを作成します。左側のポインタは配列の最初の項目を指し、右側のポインタは配列の最後の項目を指します。ピボットよりも大きい要素が見つかるまで左側のポインタを移動し、ピボットよりも小さい要素が見つかるまで右側のポインタを移動して、位置を交換します。左側のポインタが右側のポインタより先になるまで、このプロセスを繰り返します。
アルゴリズムは、配列が完全にソートされるまで、分割された小さな配列に対して手順 1 と 2 を繰り返します。

コードは次のとおりです。

 // クイックソート
クイックソート(arr,左,右) {
    インデックスを付ける 
    （arr.length > 1）の場合{
インデックス= パーティション(arr,左,右)
      if(左<インデックス- 1) {
        クイックソート(arr,左,インデックス-1)
      }
      if(インデックス<右) {
        クイックソート(arr,インデックス,右)
      }
    }
  }
 // プロセスを分割する
パーティション(arr,左,右) {
    part = arr[Math,floor(( right + left ) / 2)]とします。
        i =左、
        j =右 
    i <= j の間 {
      while(arr[i] < 部分) {
        私は++
      }
      while(arr[j] > part) {
        じ --  
      }
      i <= jの場合{
        // 交換する
        [arr[i], arr[j]] = [arr[j], arr[i]]
        私は++
        じ --  
      }
    }
戻る
}

7. シーケンシャルサーチ

検索アルゴリズムも、よく使用されるアルゴリズムの 1 つです。たとえば、ユーザーまたはデータを検索する必要がある場合、フロントエンドでもバックエンドでも検索アルゴリズムを使用します。まず、最も単純で効率の悪い順次検索を紹介しましょう。基本的な考え方は、データ構造内の各要素をクエリする要素と比較し、指定された要素のインデックスを返すことです。

シーケンシャル検索が非効率な理由は、検索する値が見つかるまで毎回クエリが配列の先頭から開始され、全体的なクエリが十分に柔軟で動的ではないためです。順次検索コードは次のように実装されます。

シーケンシャルサーチ(arr, アイテム) {
 ( i = 0 とします; i< arr.length; i++) {
      if(item === arr[i]) {
戻る
      }
    }
 -1を返す
}

次に、より一般的に使用され、柔軟性の高い検索アルゴリズムであるバイナリ検索を見てみましょう。

8. バイナリ検索

バイナリ検索のアイデアはやや「投機的」ですが、理論的根拠のある一種の「投機」です。まず、検索対象のデータ構造をソートする必要があり、次に次の処理を実行します。

配列の中央値を見つける
中央の値が検索対象の値である場合、中央の値のインデックスが直接返されます。
検索する値が中央値より小さい場合は、手順 1 に戻り、間隔範囲を狭めて、中央値の左側のサブ配列で検索を続けます。
検索する値が選択した値より大きい場合は、手順 1 に戻り、間隔の範囲を狭めて、中央の値の右側のサブ配列で検索を続けます。
見つからない場合は-1を返します

理解を容易にするために、次のスケッチを描きました。

上の図から、バイナリ検索の実装プロセスを簡単に理解できます。次に、コードの実装を見てみましょう。

バイナリサーチ(arr, アイテム) {
    // ソートアルゴリズムを呼び出して、まずデータをソートします
    this.quickSort(arr) 
 
    min = 0 とします。
最大= 配列の長さ - 1、
        中、
        エル
    while(最小値<=最大値) {
      中間 = Math.floor((最小+最大) / 2)
      el = arr[mid]
      if(el < アイテム) {
最小= 中間 + 1
      }そうでない場合 (el > 項目) {
最大= 中間 -1
      }それ以外{
戻る途中
      }
    }
 -1を返す
  }