JavaScript における一般的なソートアルゴリズムの詳細な説明

諺にこうあります:

雷鋒が雷鋒塔を倒し、Java が JavaScript を実装します。

Java に頼って普及しようとしていた JavaScript (当初は LiveScript と呼ばれていました) は、当時名前を変えて、今ではとても普及しています。 Node.js の登場により、JavaScript をフロントエンドとバックエンドの両方で使用できるようになりました。 Java は依然としてエンタープライズソフトウェア開発の分野で優位に立っていますが (C/C++ の達人の方々、私を攻撃しないでください...)、Web の世界では JavaScript が比類なくトップの座を占めています。

しかし、コンピュータアルゴリズムとデータ構造の従来の分野では、ほとんどの専門的な教科書や書籍のデフォルト言語は Java または C/C++ です。最近、アルゴリズムとデータ構造に関する知識を深めようとしており、JavaScript をデフォルト言語として使用するアルゴリズムの本を探していたため、これが私にとっては少々問題となっていました。 O'REILLYのAnimalシリーズに「JavaScriptで記述するデータ構造とアルゴリズム」という本があることを知り、ワクワクしながら2日間かけて最初から最後まで読みました。これはフロントエンド開発者向けの非常に優れたアルゴリズム入門書です。しかし、大きな欠点があります。それは、明らかな小さな誤りが多数あり、転職した私のようなプログラマーでも一目でわかるほど明らかな誤りです。もう 1 つの問題は、この本では多くの重要なアルゴリズムとデータ構造の知識が説明されていないことです。重度の強迫性障害の患者である私にとって、これらの問題は耐え難いものです。そこで、意見の相違があったときに、私は情報を探して自分でアルゴリズムを要約することにしました。さて、アルゴリズムの分野で最も基本的な知識であるソートアルゴリズムから始めましょう。

以下のコードには、自分では見つけられないバグやエラー、文法上の不規則性があるはずだと考えています。そのため、専門家にエラーを指摘してもらいたいと思っています。継続的に修正することによってのみ、長期的な進歩を遂げることができるからです。

古典的なアルゴリズムのトップ10

図で要約すると次のようになります。

用語集:

n: データサイズ

k: 「バケット」の数

インプレース: 一定のメモリを占有し、追加のメモリを占有しない

アウトプレース: 余分なメモリを消費する

安定性: ソート後の2つの等しいキー値の順序は、ソート前の順序と同じである

バブルソート

最も単純なソートアルゴリズムの 1 つであるバブルソートは、辞書に載っている Abandon と同じような感覚です。常に最初のページにあり、一番最初なので、最も馴染みがあります。。。バブルソートには、フラグを設定する最適化アルゴリズムもあります。シーケンスのトラバーサル中に要素が交換されない場合、シーケンスがすでに順序付けられていることが証明されます。しかし、この改善はパフォーマンスの向上にはあまり役立ちません。。。

最速はいつですか

入力データがすでに正の順序になっている場合 (すでに正の順序になっているのに、なぜバブルソートが必要なのでしょうか...)

一番遅いのはいつですか?

入力データが逆順の場合 (for ループを記述してデータを逆順に出力できるのに、なぜバブルソートを使用する必要があるのでしょうか。私は自由ですか...)

バブルソートアニメーションのデモンストレーション

JavaScriptコードの実装

関数bubbleSort(arr) {
    var len = arr.length;
 (var i = 0; i < len; i++)の場合{
 (var j = 0; j < len - 1 - i; j++)の場合{
            if (arr[j] > arr[j+1]) { //隣接する要素をペアで比較する
                var temp = arr[j+1]; //要素の交換
                arr[j+1] = arr[j];
                arr[j] =一時;
            }
        }
    }
 arrを返します。
 }

選択ソート

どのようなデータが入力されても時間の計算量は O(n²) であるため、最も安定したソートアルゴリズムの 1 つです。。。したがって、使用する場合、データサイズが小さいほど良いです。唯一の利点は、余分なメモリスペースを占有しないことです。

選択ソートアニメーションのデモンストレーション

JavaScriptコードの実装

関数selectionSort(arr) { 
 
    var len = arr.length; 
 
    var minIndex、 temp ; 
 
 (var i = 0; i < len - 1; i++)の場合{ 
 
        最小インデックス = i; 
 
 (var j = i + 1; j < len; j++)の場合{ 
 
            if (arr[j] < arr[minIndex]) { //最小の数値を見つける
 
                minIndex = j; //最小数のインデックスを保存する
 
            }  
        } 
 
 temp = arr[i]; 
 
        arr[i] = arr[最小インデックス]; 
 
        arr[最小インデックス] = temp ;  
    } 
 
 arrを返します。  
 }

挿入ソート

挿入ソートのコード実装はバブルソートや選択ソートほど単純で粗雑ではありませんが、その原理は最も理解しやすいはずです。ポーカーをプレイしたことがある人なら誰でも数秒で理解できるはずです。もちろん、ポーカーをプレイしているときにカードをランク順に並べることはないと言うのであれば、おそらくこの人生で挿入ソートアルゴリズムに興味を持つことはないでしょう。。。

挿入ソートには、バブルソートと同様に、半挿入と呼ばれる最適化アルゴリズムもあります。このアルゴリズムに関しては、教科書からの古典的な引用を使うのは面倒なので、「興味のある学生は授業後に自分で勉強することができます。」。。

挿入ソートのアニメーションデモンストレーション

JavaScriptコードの実装

関数挿入ソート(arr) { 
 
    var len = arr.length; 
 
    var preIndex、現在の; 
 
 (var i = 1; i < len; i++)の場合{ 
 
        プレインデックス = i - 1; 
 
現在の値= arr[i]; 
 
        preIndex >= 0 && arr[preIndex] > current の場合{ 
 
            arr[preIndex+1] = arr[preIndex]; 
 
            プレインデックス--;   
 
        } 
 
        arr[preIndex+1] =現在の; 
 
    } 
 
 arrを返します。 
 
 }

シェルソート

シェルソートは挿入ソートのより効率的な実装です。挿入ソートとは異なり、より遠い要素を優先します。シェルソートの核心は、間隔シーケンスの設定にあります。間隔シーケンスは事前に設定することも、動的に定義することもできます。間隔シーケンスを動的に定義するアルゴリズムは、アルゴリズム (第 4 版) の共著者である Robert Sedgewick によって提案されました。ここではこのアプローチを使用します。

JavaScriptコードの実装

関数shellSort(arr) { 
 
    var len = arr.length、 
 
温度、 
 
        ギャップ = 1; 
 
    while(gap < len/3) { //間隔シーケンスを動的に定義する
 
        ギャップ = ギャップ*3+1; 
 
    } 
 
ギャップの場合、ギャップ > 0、ギャップ = Math.floor(gap/3)) { 
 
 ( var i = ギャップ; i < len; i++) { 
 
 temp = arr[i]; 
 
 (var j = i-gap; j >= 0 && arr[j] > temp ; j-=gap)の場合{ 
 
                arr[j+ギャップ] = arr[j]; 
 
            } 
 
            arr[j+ギャップ] = temp ; 
 
        } 
 
    } 
 
 arrを返します。 
 
 }

マージソート

分割統治の考え方の典型的なアルゴリズムの応用として、マージソートは次の 2 つの方法で実装されます。

トップダウン再帰（すべての再帰メソッドは反復を使用して書き換えることができるため、2 番目のメソッドがあります）
ボトムアップ反復

「データ構造とアルゴリズムの JavaScript 記述」では、著者はボトムアップの反復法を紹介しています。しかし、再帰的な方法については、著者は次のように考えています。

ただし、再帰が深すぎて言語が処理できないため、JavaScript ではこれを行うことはできません。

ただし、アルゴリズムの再帰の深さが深すぎるため、JavaScript ではこれは実現できません。

正直に言うと、この文章はよく分かりません。これは、JavaScript コンパイラのメモリが少なすぎて再帰が深すぎるため、メモリオーバーフローが簡単に発生する可能性があることを意味しますか?偉大な神様が私にアドバイスを与えてくれることを願っています。

選択ソートと同様に、マージソートのパフォーマンスは入力データの影響を受けませんが、時間の計算量が常に O(n log n) であるため、選択ソートよりもはるかに優れたパフォーマンスを発揮します。コストは、必要な追加のメモリスペースです。

マージソートのアニメーションデモンストレーション

マージソートの JavaScript コードの実装:

 function mergeSort(arr) { //トップダウン再帰法を使用する
 
    var len = arr.length; 
 
    長さが2以下の場合
 
 arrを返します。 
 
    } 
 
    var middle = Math.floor(len / 2)、 
 
左= arr.slice(0, 中央)、 
 
右= arr.slice(中央); 
 
 merge(mergeSort(左), mergeSort(右))を返します。  
 } 
 
  
 
関数merge(左,右)  
 { 
 
    var 結果 = [];    
 
    while (左.長さ &&右.長さ) { 
 
        （左[0] <=右[0]）の場合{ 
 
            結果.push(左.shift()); 
 
        }それ以外{ 
 
            結果.push(右.shift()); 
 
        }  
    }   
 
    while (左.長さ) 
 
        結果.push(左.shift());  
  
 
    while (右.長さ) 
 
        結果.push(右.shift());  
  
 
結果を返します。 
 
 }

クイックソート

クイックソートは、ソートアルゴリズムにおける分割統治の考え方のもう 1 つの典型的な応用です。本質的に、クイックソートはバブルソートに基づく再帰的な分割統治法とみなされるべきです。

クイックソートという名前は単純で大雑把です。この名前を聞いた瞬間に、その存在の意味がわかります。つまり、高速で効率的です。これは、ビッグデータを処理するための最速のソートアルゴリズムの 1 つです。最悪ケースの時間計算量は O(n²) に達しますが、これは優れた結果です。ほとんどの場合、平均時間計算量が O(n log n) のソートアルゴリズムよりも優れたパフォーマンスを発揮します。しかし、その理由はわかりません。。。幸いなことに、私の強迫性障害は再発し、多くの情報を確認した後、ついに「アルゴリズムアートおよび情報科学コンテスト」で満足のいく答えを見つけました。

クイックソートの最悪ケースの実行時間は、例えばシーケンシャルシーケンスのクイックソートの場合、O(n²) です。しかし、償却予想時間は O(n log n) であり、O(n log n) 表記法で暗示される定数係数は非常に小さく、複雑性が安定して O(n log n) に等しいマージソートよりもはるかに小さくなります。したがって、弱い順序を持つほとんどの乱数シーケンスでは、クイックソートがマージソートよりも常に優れています。

クイックソートアニメーションのデモンストレーション

クイックソートの JavaScript コードの実装:

関数quickSort(arr, left , right ) { 
 
    var len = arr.length、 
 
        パーティションインデックス、 
 
左= typeof左!= 'number' ? 0 :左、 
 
 right = typeof right != 'number' ? len - 1 : right ; 
 
    （左<右）の場合{ 
 
        パーティションインデックス = パーティション(arr、左、右); 
 
        クイックソート(arr,左, パーティションインデックス-1); 
 
        クイックソート(arr、パーティションインデックス+1、右); 
 
    } 
 
 arrを返します。 
 
 } 
 
 function partition(arr, left , right ) { //パーティション操作
 
    var pivot = left , //ピボット値を設定する
 
インデックス= ピボット + 1; 
 
 (var i =インデックス; i <=右; i++) { 
 
        （arr[i] < arr[pivot]）の場合{ 
 
            swap(arr, i,インデックス); 
 
インデックス++; 
 
        } 
 
    } 
 
    swap(arr, ピボット,インデックス- 1); 
 
戻る インデックス-1; 
 
 } 
 
関数swap(arr, i, j) { 
 
    var temp = arr[i]; 
 
    arr[i] = arr[j]; 
 
    arr[j] =一時; 
 
 }

ヒープソート

ヒープソートは、ヒープの概念を使用してソートする選択ソートであると言えます。方法は2つあります。

最大トップヒープ: 各ノードの値は、その子ノードの値以上であり、ヒープソートアルゴリズムで昇順でソートするために使用されます。
ミニトップヒープ: 各ノードの値は、その子ノードの値以下であり、ヒープソートアルゴリズムの降順のために使用されます。

ヒープソートアニメーションのデモンストレーション

ヒープソートの JavaScript コードの実装:

 var len; //宣言された複数の関数はデータ長を必要とするため、lenはグローバル変数として設定されます
 
 function buildMaxHeap(arr) { //最大ヒープを構築する
 
    len = 配列の長さ; 
 
 (var i = Math.floor(len/2); i >= 0; i -- ) {   
 
        ヒープ化(arr, i); 
 
    }
 }
 function heapify(arr, i) { //ヒープ調整
 
    var左= 2 * i + 1、 
 
右= 2 * i + 2、 
 
        最大 = i; 
  
 
    if ( left < len && arr[ left ] > arr[largest]) { 
 
        最大 =左; 
 
    } 
 
    if ( right < len && arr[ right ] > arr[largest]) { 
 
        最大 =右; 
 
    } 
 
    （最大 != i）の場合{ 
 
        swap(arr, i, 最大); 
 
        ヒープ化(arr, 最大);
    }
 } 
 
関数swap(arr, i, j) { 
 
    var temp = arr[i]; 
 
    arr[i] = arr[j]; 
 
    arr[j] =一時; 
 
 } 
 
関数heapSort(arr) { 
 
    ビルドMaxHeap(arr); 
 
 (var i = arr.length-1; i > 0; i --) {   
 
        スワップ(arr, 0, i); 
 
        長さ--;   
 
        ヒープ化(arr, 0);
    } 
 
 arrを返します。
 }

カウントソート

カウンティングソートの中核は、入力データの値をキーに変換し、それを追加の配列スペースに格納することです。線形時間計算量を持つソート方法として、カウンティングソートでは、入力データが特定の範囲の整数である必要があります。

カウントソートアニメーションデモンストレーション

カウントソートの JavaScript コードの実装:

関数countingSort(arr, maxValue) {
    var バケット = 新しい配列(maxValue+1)、
        ソートインデックス = 0;
        arrLen = arr.長さ、
        バケット長さ = 最大値 + 1; 
 
 (var i = 0; i < arrLen; i++)の場合{
        if (!bucket[arr[i]]) {
            バケット[arr[i]] = 0;
        }
        バケット[arr[i]]++;
    } 
 
 ( var j = 0; j < バケット長さ; j++) {
        while(バケット[j] > 0) {
            arr[ソートされたインデックス++] = j;
            バケット[j] --;  
        }
    } 
 
 arrを返します。
 }

バケットソート

バケットソートは、カウントソートのアップグレード版です。これは関数のマッピング関係を利用しますが、その効率の鍵はこのマッピング関数の決定にあります。

バケットソートをより効率的にするには、次の 2 つのことを行う必要があります。

十分な余裕がある場合は、バケットの数を増やしてみてください
使用されるマッピング関数は、N 個の入力データを K 個のバケットに均等に分散できます。

同時に、バケット内の要素のソートでは、比較ソートアルゴリズムの選択がパフォーマンスに大きく影響します。

最速はいつですか

入力データが各バケットに均等に分散できる場合

一番遅いのはいつですか?

入力データが同じバケットに割り当てられている場合

バケットソートの JavaScript コードの実装:

関数bucketSort(arr,bucketSize) {
    （arr.length === 0）の場合{
 arrを返します。
    } 
  
    var 私;
    var 最小値 = arr[0];
    var 最大値 = arr[0];
 (i = 1; i < arr.length; i++)の場合{
      （arr[i] < 最小値）の場合{
          minValue = arr[i]; //入力データの最小値
      }そうでなければ(arr[i] > maxValue) {
          maxValue = arr[i]; //入力データの最大値
      }
    } 
  
    //バケットの初期化
    var DEFAULT_BUCKET_SIZE = 5; //デフォルトのバケット数を5に設定する
    バケットサイズ = バケットサイズ || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    var バケット = 新しい配列(bucketCount);
 ( i = 0; i < バケットの長さ; i++) {
        バケット[i] = [];
    } 
  
    //マッピング関数を使用して各バケットにデータを分配する
(i = 0; i < arr.length; i++)の場合{
        バケット[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    } 
  
    arr.長さ = 0;
 ( i = 0; i < バケットの長さ; i++) {
        insertionSort(buckets[i]); //挿入ソートを使用して各バケットをソートする
( var j = 0; j < バケット[i].length; j++) {
            arr.push(バケット[i][j]);
        }
    } 
  
 arrを返します。
 }

基数ソート

基数ソートには2つの方法がある

MSDは最上位ビットからソートする
LSDは最下位ビットからソートする

基数ソート vs カウンティングソート vs バケットソート

これら 3 つのソートアルゴリズムはすべてバケットの概念を使用しますが、バケットの使用方法には明らかな違いがあります。

基数ソート: キー値の各桁に応じてバケットを割り当てる
カウントソート: 各バケットには1つのキー値のみが格納されます
バケットソート: 各バケットには特定の範囲の値が格納されます

LSD 基数ソートのアニメーションデモンストレーション:

基数ソートの JavaScript コード実装:

 //LSD 基数ソート
var カウンタ = [];
関数radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
 ( var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
 (var j = 0; j < arr.length; j++)の場合{
            var バケット = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null ) {
                カウンター[バケット] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
 (var j = 0; j < counter.length; j++)の場合{
            var 値 = null ;
            カウンタ[j]!= nullの場合{
                while ((値 = counter[j].shift()) != null ) {
                      arr[pos++] = 値;
                }
          }
        }
    }
 arrを返します。
 }