主要なソートアルゴリズムのパフォーマンス比較とデモンストレーション例

ソートとは、もともと無秩序だったシーケンスを、順序のあるシーケンスに並べ替えることを意味します。

ソート方法には安定性が関係しています。いわゆる安定性とは、ソートするシーケンスに 2 つ以上の同一の項目がある場合、ソートの前後でこれらの同一の項目の相対的な位置がチェックされ、変化があるかどうかが調べられることを意味します。変化がない場合、ソート方法は安定しています。変化がある場合、ソート方法は不安定であることを意味します。

レコード内のキーワードが繰り返されない場合、ソート結果は一意であり、選択したソート方法が安定しているかどうかは問題ではありません。キーワードが繰り返される場合、ソート方法を選択するときに、特定のニーズに基づいて安定したソート方法を選択するか、不安定なソート方法を選択するかを検討する必要があります。では、どのソートアルゴリズムが不安定なのでしょうか?

「高速、一部、選択ヒープ」： 「高速」はクイックソート、「一部」はシェルソート、「選択」は選択ソート、「ヒープ」はヒープソートを指します。つまり、これら 4 つのソート方法は不安定であり、その他のソート方法は自然に安定しています。

ソートアルゴリズムの分類

1. 挿入ソート

つまり、すでに整列したシーケンスに新しいレコードを挿入することは、軍事訓練で整列するようなものです。すでに列が形成されており、そこに新しいメンバーが加わると、その新しいメンバーはチーム内の適切な位置に「挿入」されます。このタイプのソートには、直接挿入ソート、バイナリ挿入ソート、シェルソートが含まれます。

2. 取引所の仕分け

このタイプの方法の核心は「交換」です。つまり、各ソートは一連の「交換」アクションを通じて完了します。たとえば、軍事訓練の列に並んでいるとき、インストラクターは次のように言います。「あなたは隣の人よりも背が高いです。あなたたち2人は交換してください。それでも隣の人よりも背が高い場合は、交換を続けます。」このタイプのソートには、バブルソートとクイックソートが含まれます。

3. クラスソートを選択

この方法の核となるのは「選択」です。つまり、ソート処理のたびに最小 (または最大) のレコードが選択され、シーケンス内の最初の (または最後の) レコードと交換され、最小 (または最大) のレコードが配置されます。例えば、軍事訓練のために整列するとき、教官は最も小さい生徒を選び、最後の位置にいる生徒と位置を交換するように指示し、残りの生徒は選択を続けます。このタイプのソートには、選択ソートとヒープソートが含まれます。

4. マージクラスのソート

いわゆるマージとは、2 つ以上の順序付けられたシーケンスを新しい順序付けられたシーケンスに結合することです。例えば、軍事訓練で整列する際、教官は次のように言っています。「まず、全員が隣の人とペアになり、そのグループの中に並びます。そのペアと隣のペアは4人組になり、そのグループの中に並びます。これを繰り返し、すべての生徒が1つのグループに統合されて整列します。」このタイプのソートには、(双方向) マージソートが含まれます。

5. カーディナリティソート

このタイプの方法は非常に特殊です。これは、論理キーワードを複数のキーワードに分割する、マルチキーワードソートの考え方に基づいています。たとえば、トランプのデッキは、基数ソートの考え方に従って最初にスーツでソートし、次に 4 つの山に分けることができます。次に、各山を AK の順序でソートして、最終的にトランプのデッキ全体が整列するようにします。

ソートアルゴリズム分析

この記事で分析する主なソートアルゴリズムは、バブルソート、選択ソート、挿入ソート、シェルソート、クイックソート、マージソート、ヒープソートです。

交換アルゴリズム

ほとんどのソートアルゴリズムは 2 つのレコードを交換するアクションを使用するため、さまざまなソートアルゴリズムの使用を容易にするために、交換アクションは個別にカプセル化されます。

//スワップ関数 
 Array.prototype.swap = 関数(i, j) {
  var temp = this [i];
これ[i] =これ[j];
 this [j] = 一時;
 }

挿入ソート

アルゴリズムのアイデア: 各ラウンドで、ソートするキーワードは、挿入が完了するまで、そのキーワード値のサイズに応じて、ソートされた部分シーケンスの適切な位置に挿入されます。

// ソートを挿入 
 Array.prototype.insertionSort = 関数() {
 (var i = 1 ; i < this .length; ++i)の場合
    {
        var j = i,
            値 = this [i];
 (j > 0 && this [j - 1 ] > 値)の間
        {
これ[j] =これ[j - 1 ];
            --j;
        }
 this [j] = 値;
    }
 }

アルゴリズムのパフォーマンス: 内部ループでは、this[j]=this[j-1]が基本操作です。最悪の場合、つまりシーケンス全体が逆順である場合、基本操作の実行回数は合計で n*(n-1)/2 となり、時間の計算量は O(n*n) となります。最良のケース、つまりシーケンス全体がすでに順序付けられている場合、ループ内の操作はすべて一定レベルであり、その時間計算量は O(n) であるとします。したがって、このアルゴリズムの平均時間計算量は O(n*n) です。このアルゴリズムでは追加の値が 1 つだけ必要なので、空間計算量は O(1) です。

シェルソート

アルゴリズムのアイデア: シェルソートは縮小増分ソートとも呼ばれ、ソートするシーケンスを特定の規則に従っていくつかのサブシーケンスに分割し、これらのサブシーケンスを個別に挿入してソートします。この規則は増分です。たとえば、5、3、1 の増分を使用してシーケンスを分割し、各シェルソートの増分を徐々に減らすことができます。シェルソートの各ソートにより、シーケンス全体がより整然としたものになります。シーケンス全体が基本的に整然としたら、別の挿入ソートを使用すると、より効率的になります。これがシェルソートの考え方です。

// シェルソート 
 Array.prototype.shellSort = 関数() {
 (var step = this .length >> 1 ; step > 0 ; step >>= 1 )の場合
    {
 (var i = 0 ; i < ステップ; ++i)の場合
        {
 (var j = i + step; j < this .length; j += step)の場合
            {
                var k = j、値 = this [j];
 while (k >= ステップ && this [k - ステップ] > 値)
                {
 this [k] = this [k - ステップ];
                    k -= ステップ;
                }
 this [k] = 値;
            }
        }
    }
 }

アルゴリズムのパフォーマンス: シェルソートの平均時間計算量は O(nlogn) で、空間計算量は O(1) です。シェルソートで増分を取るときは、まず増分シーケンスの最後の値が 1 でなければならないことに注意してください。次に、増分シーケンスの値には 1 以外の共通因数がないことが必要です。たとえば、8、4、2、1 のようなシーケンスは取らないでください (共通因数は 2 です)。

バブルソート

アルゴリズムの考え方: 一連の「交換」アクションによって完了します。まず、最初のレコードが 2 番目のレコードと比較されます。最初のレコードの方が大きい場合は、2 つのレコードが交換され、そうでない場合は交換されません。次に、2 番目のレコードが 3 番目のレコードと比較されます。2 番目のレコードの方が大きい場合は、2 つのレコードが交換され、そうでない場合は交換されません。最後に、最初のレコードが最後のレコードと交換され、バブルソートが完了します。この過程で、大きなレコードは石のように底に沈み、小さなレコードは徐々に浮かび上がってきます。バブルソートアルゴリズムが終了する条件は、1 回のソートパスで要素の交換が発生しないことです。

//バブルソート 
 Array.prototype.bubbleSort = 関数() {
 (var i = this .length - 1 ; i > 0 ; --i)の場合
    {
 (var j = 0 ; j < i; ++j)の場合
もし( this [j] > this [j + 1 ])
これを.swap(j, j + 1 );
    }
 }

アルゴリズムのパフォーマンス: 最も内側のループでの要素交換操作は、アルゴリズムの基本的な操作です。最悪の場合、ソートするシーケンスが逆順になっていると、基本操作の実行回数は合計で (n-1+1)*(n-1)/2=n(n-1)/2 となり、時間の計算量は O(n*n) になります。最良の場合、ソートするシーケンスが順序どおりになっていると、時間の計算量は O(n) となり、平均的な場合の時間の計算量は O(n*n) になります。アルゴリズムの追加の補助空間は交換に使用される 1 つのテンポラリのみなので、空間計算量は O(1) です。

クイックソート

アルゴリズムのアイデア: 軍事訓練の列を例にとると、インストラクターは、*** 番目の生徒が中央に立ち、彼より背の低い生徒は彼の左側に、背の高い生徒は彼の右側に立つように指示します。これはクイックソートです。したがって、クイックソートでは、ピボットを使用してシーケンスを 2 つの部分に分割します。ピボットの片側はピボットより小さく (またはそれ以下)、もう片側はピボットより大きくなります (またはそれ以上)。

// 再帰クイックソート 
 Array.prototype.quickSort = function(s, e) {
 s == nullの場合
        s = 0 ;
 e == nullの場合
        e = this .length - 1 ;
もし(s >= e)
戻る;
これは.swap((s + e) >> 1 , e);
    var インデックス = s - 1 ;
 (var i = s; i <= e; ++i)の場合
this [i] <= this [e] の場合this .swap(i, ++index) ;
 this .quickSort(s, index - 1 );
これは.quickSort(index + 1 , e);
 }

アルゴリズムのパフォーマンス: クイックソートの時間計算量は、最良の場合で O(nlogn) です。ソートするシーケンスが無秩序に近いほど、アルゴリズムは効率的になります。最悪の場合、時間計算量は O(n*n) です。ソートするシーケンスが順序に近いほど、アルゴリズムの効率は低くなります。アルゴリズムの平均時間計算量は O(nlogn) です。平均時間で見ると、クイックソートはすべてのソートアルゴリズムの中で最も高速です。このアルゴリズムの空間計算量は O(logn) です。クイックソートは再帰的に実行され、スタックの支援を必要とするため、以前のソート方法よりも多くの補助スペースが必要になります。

クイックソートの効率は、選択した「ピボット」に関係しています。選択したピボットが中央値に近いほど、アルゴリズムの効率が高くなります。したがって、アルゴリズムの効率を向上させるために、最初に「ピボット」を選択するときに、サンプリングと同様に、データパイルからランダムに 3 つの値を選択し、その 3 つの値の平均を「ピボット」として取得するなど、いくつかの変更を加えることができます。クイックソートアルゴリズムの効率を向上させる方法については、この記事では詳しく説明せず、ここで終わります。（興味のある読者は自分で調べてください）

選択ソート

アルゴリズムのアイデア: このアルゴリズムの主なアクションは「選択」です。単純な選択方法を使用して、シーケンスを最初から最後までスキャンし、最小のレコードを見つけて最初のレコードと交換し、残りのレコードからこの選択と交換を続行して、最終的にシーケンスを順序付けます。

//並べ替えを選択 
 Array.prototype.selectionSort = 関数() {
 (var i = 0 ; i < this .length; ++i)の場合
    {
        var インデックス = i;
 (var j = i + 1 ; j < this .length; ++j)の場合
        {
 if ( this [j] < this [index])
                インデックス = j;
        }
これを.swap(i, インデックス);
    }
 }

アルゴリズムのパフォーマンス: 最も内側のループの比較を基本操作とすると、その実行時間は (n-1+1)*(n-1)/2=n(n-1)/2 となり、時間計算量は O(n*n) となります。このアルゴリズムには temp という余分なスペースが 1 つだけあるため、スペース計算量は O(1) となります。

ヒープソート

アルゴリズムの考え方: ヒープはデータ構造です。ヒープを理解する最も良い方法は、完全な二分木として考えることです。この完全な二分木は、葉以外のノードの値が、その左と右の子ノードの値より大きくない (または小さくない) という条件を満たします。父親が年上で子供が年下の場合、そのようなヒープは大きなトップヒープと呼ばれます。父親が年下で子供が年上の場合、そのようなヒープは小さなトップヒープと呼ばれます。ヒープ定義によれば、ルートノードの値が最大（または最小）であるため、順序付けされていないシーケンスをヒープに調整することで、シーケンスの最大（または最小）値を見つけ、見つかった値をシーケンスの最大（または先頭）の値と交換できます。このようにして、順序付けされたシーケンスの要素数は 1 増加し、順序付けされていないシーケンスの要素数は 1 減少します。この操作を新しい順序付けされていないシーケンスに対して繰り返すと、シーケンスのソートが実現されます。ヒープソートにおける最も重要な操作は、シーケンスをヒープに調整することです。ソートプロセス全体は、ヒープの定義に準拠していない完全なバイナリツリーを、ヒープの定義に準拠した完全なバイナリツリーに継続的に調整するプロセスです。

ヒープソート実行プロセス（大きなトップヒープ）:

（１）順序付けられていないシーケンスによって決定された完全な二分木の最初の非葉ノードから始めて、各ノードを右から左へ、下から上に調整すると、最終的に大きなトップヒープが得られます。現在のノード (a) の値をその子ノードと比較します。値が a より大きい子ノードがある場合は、その最小値を選択して a と交換します。 a が次の層に来ると、a の子ノードの値がすべて a の値よりも小さくなるまで上記のプロセスが繰り返されます。

（２）現在の順序なしシーケンスの最初の要素（ツリーのルートノード（a））を、順序なしシーケンスの最後の要素（b）と交換します。 a は順序付きシーケンスに入り、最終位置に到達します。順序なしシーケンスの要素は 1 減少し、順序付きシーケンスの要素は 1 増加します。このとき、ノード b のみがヒープ定義を満たさない可能性があるため、調整されます。

（３）順序なしシーケンスに要素が１つだけ残るまで手順２を繰り返します。

//ヒープソート 
 Array.prototype.heapSort = 関数() {
 (var i = 1 ; i < this .length; ++i)の場合
        {
 (var j = i, k = (j - 1 ) >> 1 ; k >= 0 ; j = k, k = (k - 1 ) >> 1 )の場合
        {
もし(これ[k] >=これ[j])
壊す;
これを.swap(j, k);
        }
    }
 (var i = this .length - 1 ; i > 0 ; --i)の場合
    {
これを.swap( 0 , i);
 (var j = 0 、 k = (j + 1 ) << 1 ; k <= i; j = k、 k = (k + 1 ) << 1 )の場合
        {
 (k == i || this [k] < this [k - 1 ])の場合
                --k;
もし(これ[k] <=これ[j])
壊す;
これを.swap(j, k);
        }
    }
 }

アルゴリズムのパフォーマンス: 完全な二分木の高さは [log(n+1)] です。つまり、各ノードを調整する時間の計算量は O(logn) です。基本操作の総数は、2 つの並列ループの基本操作の数の合計です。アルゴリズム全体の時間の計算量は O(logn)*n/2+O(logn)*(n-1)、つまり O(nlogn) です。余分なスペースは temp だけなので、スペースの複雑さは O(1) です。

ヒープソートの利点は、1,000,000 件のレコードから上位 10 件の小さいレコードを選択するなど、レコード数が多いシナリオに適していることです。この場合、ヒープソートが最適です。レコード数が少ない場合は、ヒープソートは推奨されません。また、ハッシュテーブル + ヒープソートは、大量データの処理に最適な組み合わせです。大量データ処理については、今後のブログ投稿で紹介する予定です。

マージソート

アルゴリズムのアイデア: その核心は「2 つずつマージ」です。まず、元のシーケンスを、それぞれ 1 つの要素のみを含むサブシーケンスと見なします。2 つずつマージして、順序付けられた 2 つのタプルをいくつか形成します。これで、マージソートの最初のラウンドが完了します。次に、このシーケンスをいくつかの 2 つのタプルのサブシーケンスと見なします。2 つずつマージを続けて、順序付けられた 4 つのタプルをいくつか形成します。これで、マージソートの 2 回目のラウンドが完了します。以下同様に続きます。サブシーケンスが 2 つだけになったら、もう一度マージしてマージソート全体を完了します。

//マージソート 
 Array.prototype.mergeSort = 関数(s, e, b) {
 s == nullの場合
        s = 0 ;
 e == nullの場合
        e = this .length - 1 ;
 b == nullの場合
        b =新しい配列( this .length);
もし(s >= e)
戻る;
    var m = (s + e) >> 1 ;
これは.mergeSort(s, m, b);
これは.mergeSort(m + 1 , e, b);
 (変数 i = s、j = s、k = m + 1 ; i <= e; ++i)の場合
        b[i] = this [(k > e || j <= m && this [j] < this [k]) ? j++ : k++];
 (var i = s; i <= e; ++i)の場合
これは[i] = b[i]です。
 }

アルゴリズムのパフォーマンス: 基本操作として「マージ操作」を選択できます。「マージ操作」は、マージするテーブル内の要素を、マージ結果を格納するテーブルにコピーするプロセスです。回数は、マージする 2 つのサブシーケンス内の要素数の合計です。このアルゴリズムは合計で logn 回のソートパスを実行する必要があり、各ソートパスでは n 個の基本操作が実行されます。したがって、マージソート全体で実行される基本操作の合計数は nlogn です。つまり、時間の計算量は O(nlogn) です。つまり、マージソートの時間計算量は初期シーケンスに依存しません。マージソートではソートするシーケンス全体を転送する必要があるため、空間計算量は O(n) になります。

いくつかの結論

（１）クイックソート、シェルソート、マージソート、ヒープソートの平均時間はO(nlogn)であり、その他の平均時間はO(n*n)である。

（２）クイックソート、シェルソート、選択ソート、ヒープソートは不安定であるが、その他は安定している。

（３）バブルソート、クイックソート、選択ソート、ヒープソートは、１回のソートパスで要素が最終位置に到達することを保証できるソートである。

（４）選択ソートとバイナリ挿入ソートは、要素の比較回数が元の順序に依存しないソートである。

（５）ソートパスの数は、元のシーケンス（交換型ソート）と関連している。

（６）直接挿入ソートと二分挿入ソートの違いは挿入位置を見つける方法である。一方は順次探索法であり、もう一方は二分探索法である。

<<: アルゴリズムの視覚化: 理解しにくいコードをゴッホの星空に描く

>>: ディープラーニングの深層: モデリング知識とオープンソースツールのオプション