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

序文

最近、アルゴリズムの基礎を固めるために、アルゴリズムの本にある基本的なアルゴリズムをもう一度見直し、フロントエンドエンジニアが知っておく必要のあるソートアルゴリズムと検索アルゴリズムの知識を特にまとめました。理解すべき高度なアルゴリズムはまだたくさんありますが、基本を固める必要があります。この記事では、画像とテキストの形式で次のアルゴリズムの知識を紹介します。読んだ後、皆さんが何かを得られることを願っています：バブルソートとその最適化、選択ソート、挿入ソート、マージソート、クイックソート、シーケンシャルサーチ*バイナリサーチ。

[[421699]]

文章

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

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

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

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

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

バブルソートの考え方は、隣接する 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 番目に配置する、というものです。

以前のパターンに従い、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]]
      }
    }
リターン
}

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

挿入ソート

挿入ソートの考え方は、最初の項目がソートされていると仮定して、一度に 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 ミリ秒です。

マージソート

マージソートアルゴリズムは上記の 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;
    while(l <左の長さ && r <右の長さ) {
      if(左[l] <右[r]) {
        result.push(左[l++])
      }それ以外{
        result.push(右[r++])
      }
    }
    while(l <左.length) {
      result.push(左[l++])
    }
    while(r <右.length) {
      result.push(右[r++])
    }
結果を返す
}

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

クイックソート

クイックソートは、現在よく使われているソートアルゴリズムです。その複雑度は O(nlog^n) で、他の O(nlog^n) 複雑度よりもパフォーマンスが優れています。また、元の配列を分割するために分割統治の考え方を採用しています。クイックソートは実装が比較的複雑なので、その考え方は次のとおりです。1. 配列から中央の項目をピボットとして選択します。2. 2 つのポインターを作成します。左側のポインターは配列の最初の項目を指し、右側のポインターは配列の最後の項目を指します。ピボットより大きい要素が見つかるまで左のポインターを移動し、ピボットより小さい要素が見つかるまで右のポインターを移動してから、それらの位置を交換します。このプロセスを、左のポインターが右のポインターを超えるまで繰り返します。3. アルゴリズムは、分割された小さな配列に対して手順 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]]
        私は++
        じ --  
      }
    }
戻る
}

シーケンシャルサーチ

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

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

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

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

バイナリ検索

バイナリ検索のアイデアはやや「投機的」ですが、理論的根拠のある一種の「投機」です。まず、検索対象のデータ構造がソートされている必要があり、次のように処理されます。1. 配列の中央の値を検索します。2. 中央の値が検索対象の値である場合は、中央の値のインデックスを直接返します。3. 検索対象の値が中央の値よりも小さい場合は、手順 1 に戻り、間隔の範囲を狭めて、中央の値の左側のサブ配列で検索を続けます。4. 検索対象の値が選択した値より大きい場合は、手順 1 に戻り、間隔の範囲を狭めて、中央の値の右側のサブ配列で検索を続けます。5. 見つからない場合は、-1 を返します。

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

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