私たちはこれらのソートアルゴリズムを本当に理解しているのでしょうか?

[[379394]]

おそらく、あなたはすでにこれらの一般的なソートアルゴリズムを学んだことがあるか、他の人が書いた記事を読んだことがあるでしょう。しかし、この記事は間違いなくあなたの時間を無駄にすることはなく、間違いなく何かを得ることになるでしょう。

序文

中国の旧正月が近づいており、ユアンシェフは、全員が家に帰って良い新年を過ごせるように、ユアンズレストランの同僚全員に年末ボーナスを支給することを考えています。レストランのウェイターのエルダンを家に帰らせて、妻を見つけさせなさい。

元吉レストラン内

袁シェフ：店員さん、もうすぐ春節がやってきます。当店では、全員に年末ボーナスを支給します。当店の小さな小豆と黒豆のノートを見て、全員にいくら年末ボーナスを支給すべきか確認し、金額に応じて小さいものから大きいものまで並べ、順番に一人ずつお金を渡してください。皆さん、家に帰って良い新年をお過ごしください。あなたはもう子供ではありません。帰って結婚すべきです。

ウェイター：わかりました、ボス。すぐに行きます。

本日は、上記の少量から大量への整理、つまり「仕分け」についてお話します。

分類は、私たちが生活の中で頻繁に直面する問題です。体育の授業では、先生が背の低い順に並べます。大学院入試では、合計点数に応じて点数の高い順に分類されます（大学院入試を受ける読者の皆さん、きっと志望校から大きな封筒が送られてくるでしょう）。オンラインで買い物をするとき、期待に最も合った商品を、販売量の多い順、価格の安い順に並べることがあります。これらはすべて私たちの生活の中の例です。

ソートの概念: 特定の方法 (ソート アルゴリズム) によって、整理されていないデータ要素をキーワード順に並べるプロセスをソートと呼びます。例えば、上記の販売量や価格などがキーワードとなります。

ソートアルゴリズムの安定性

ソートアルゴリズムの安定性とは何ですか?

ソートするレコード シーケンスに同じキーワードを持つレコードが 2 つ以上ある場合、ソート結果が一意にならないことがあります。そのため、ソート後、等しい要素の元の順序は変更されません。ソート方法が安定している場合、それは不安定と呼ばれます。下の図をご覧ください

たとえば、上の図では、配列に 2 つの同一の要素 4 があります。これらをソートするには、異なるソート アルゴリズムを使用します。アルゴリズム 1 でソートした後、2 つの同一の要素の相対的な位置は変わりません。これを安定したソート アルゴリズムと呼びます。アルゴリズム 2 でソートした後、相対的な位置が変わります。これは不安定なソート アルゴリズムです。

では、ソートアルゴリズムの安定性は何の役に立つのでしょうか?

問題を練習するときは、主に配列をソートするだけで、時間計算量や空間計算量などの指標のみを考慮する必要があります。ソートアルゴリズムが安定しているかどうかは、通常考慮されません。しかし、実際のソフトウェア開発では、ソートアルゴリズムの安定性は特に重要な指標となります。前の例を続けましょう。年末ボーナスを少ないものから多いものの順に並べ替え、同じ年末ボーナスの範囲内の小豆の数を少ないものから多いものの順に並べ替えます。

ここではソートアルゴリズムの安定性が重要です。なぜでしょうか？下の写真をご覧ください。

最初の仕分けが終わると、従業員全員が小豆の数に応じて少ない順から多い順に仕分けされます。

2 回目のソートでは、安定したソートアルゴリズムを使用しているため、2 回目のソート後も、同じ年末ボーナスを受け取った従業員は小豆の順序を維持します (相対的な位置は変更されません)。また、小豆は小さいものから大きいものの順にソートされたままです。 2 回のソートのみを必要とする安定したソート アルゴリズムを使用します。

安定したソートにより、最初のキーワード ソートの結果が、2 番目のキーワード ソートで等しい値を持つ数値として提供されます。

上記の状況では、不安定なソートアルゴリズムを使用すると、この効果を達成するのは非常に複雑になります。

比較クラスと非比較クラス

要素の相対的な順序は、他の要素との比較に依存するかどうかに基づいて決定します。これは、比較ソート アルゴリズムと非比較ソート アルゴリズムを区別するために使用されます。

内部および外部の選別

内部ソートとは、ソート処理全体を通じて、ソート対象となるすべてのレコードがメモリ内に配置されることを意味します。外部ソートは、ソートするレコードの数が多すぎて、同時にメモリに配置することができないために行われます。ソート プロセス全体では、内部メモリと外部メモリの間で複数のデータ交換が必要になります。一般的な内部ソート アルゴリズムには、挿入ソート、シェル ソート、選択ソート、バブル ソート、マージ ソート、クイック ソート、ヒープ ソート、基数ソートなどがあります。

内部ソートでは、主に時間パフォーマンス、補助スペース、アルゴリズムの複雑さという 3 つの側面が影響を受けます。

時間パフォーマンス

ソート アルゴリズムの実行中、比較と交換という 2 つの主要な操作が実行されます。比較はソート アルゴリズムの最も基本的な操作であり、移動はレコードをある位置から別の位置に移動することを指します。したがって、効率的なソートアルゴリズムでは、比較と移動をできるだけ少なくする必要があります。

補助スペース

アルゴリズムを実行するために必要な補助スペースの量も、ソート アルゴリズムのパフォーマンスを測定する重要な指標です。

アルゴリズムの複雑さ

ここでのアルゴリズムの複雑さは、アルゴリズムの時間的複雑さではなく、アルゴリズム自体の複雑さを指します。過度に複雑なアルゴリズムは、ソートのパフォーマンスにも影響します。

これまで見落としていた点がないか確認するために、バブル ソートと単純選択ソートという 2 つの単純なソート アルゴリズムを確認してみましょう。後ほど連載を続け、一般的な実用的なソートアルゴリズムをすべてまとめます。

バブルソート

さまざまなアルゴリズムの本でソートを学ぶとき、おそらく最初に思い浮かぶのはバブルソートでしょう。一番の理由は、このソートアルゴリズムの考え方が一番シンプルで、一番わかりやすいからです（名前の響きがいいからというのもあるかもしれませんが、笑）。習ったことがある人も一緒に復習できます。一緒にバブルソートを深掘りしていきましょう。

バブルソートの基本的な考え方は、隣接するレコードのキーワードをペアで比較し、逆順になっている場合は逆順がなくなるまで交換することです。バブルソートでは、少なくとも 1 つの要素が 1 つのバブル内の適切な位置に移動します。そのため、配列に n 個の要素がある場合、ソートは n 回繰り返すと完了します。定義によれば、バブルソートは明らかに比較ソートです。

最も単純なソートの実装

まずはこのコードを見てみましょう

クラスソリューション{
公共  int [] sortArray( int [] 数値) {
 int len ​​= nums.length;
 ( int i = 0; i < len; ++i)の場合{
 ( int j = i+1; j < len; ++j)の場合{
                （数値[i] > 数値[j]）の場合{
                    swap(数値、i、j);
                }
            }
        }
数値を返します。 
          
    }
パブリックvoid swap( int [] 数値、 int i、 int j) {
整数  temp = 数値[i];
        数値[i] = 数値[j];
        数値[j] = temp ;
    }
 }

上記のコードについて考えてみましょう。キーワード nums[i] と nums[j] を比較するたびに、nums[i] > nums[j] の場合はそれらを交換します。このように、1 回のループの後には nums[0] が最小値になるはずです。

では、このコードはバブル ソートでしょうか? 明らかに違います。バブル ソートの考え方は、隣接するレコードのキーワードを 2 つずつ比較することです。隣接するレコードがあるため、このコードはバブル ソートではないことに注意してください。次に、動的ダイアグラムを使用してバブル ソートの実行プロセスをシミュレートします。これを読めば、本格的なバブル ソートを記述できるようになります。

バブルソートコード

クラスソリューション{
公共  int [] sortArray( int [] 数値) {
 int len ​​= nums.length;
 ( int i = 0; i < len; ++i)の場合{
 ( int j = 0; j < len - i - 1; ++j) {
                （数値[j] > 数値[j+1]）の場合{
                    swap(数値、j、j+1);
                }
            }
        }
数値を返します。
    }
パブリックvoid swap( int [] 数値、 int i、 int j) {
整数  temp = 数値[i];
        数値[i] = 数値[j];
        数値[j] = temp ;
    }
 }

上図のコードは本物のバブルソートコードですが、この問題は見つかりましたか?

この時点で、配列は完全に順序付けられ、直接返すことができますが、アニメーションは返されず、実行が継続されます。では、完全に順序付けられ、実行を継続せずに直接返すにはどうすればよいのでしょうか。

nums[j] と nums[j+1] を比較し、大きい場合はそれらを交換するとします。完全に順序付けられた配列の場合は、バブルソートを実行し、比較するたびに交換する必要がないとします。交換が行われない場合は、現在の注文が完了したことを意味します。

スワップが発生したかどうかを判断するためにフラグを使用できますか? もちろん可能です。

バブルソートを改良しよう

改良されたバブルソートコード

クラスソリューション{
公共  int [] sortArray( int [] 数値) {
 int len ​​= nums.length;
        // フラグビット
        ブールフラグ = true ;
        // forループの条件に注意してください
( int i = 0; i < len && flag; ++i)の場合{
            //交換が行われない場合は、まだfalseとなり、次回ループは終了します。
            フラグ = false ;
 ( int j = 0; j < len - i - 1; ++j) {
                （数値[j] > 数値[j+1]）の場合{
                    swap(数値、j、j+1);
                    //交換が発生した場合はそれが真となり、次回も判定が継続されます
                    フラグ = true ;
                }
            }
        }
数値を返します。
    }
パブリックvoid swap ( int [] 数値、 int i、 int j) {
整数  temp = 数値[i];
        数値[i] = 数値[j];
        数値[j] = temp ;
    }
 }

このようにして、順序がすでにある場合に、意味のない循環的な判断を回避します。

時間計算量分析

最適なケースは、ソートするテーブルが完全に順序付けられている場合です。改善されたコードによれば、必要な走査は 1 回だけ、比較は n -1 回だけ、時間の計算量は O(n) です。

最悪の場合、つまりソート対象のリストが逆順になっている場合は、(n-1) + (n-2) +.... + 2 + 1 = n*(n-1)/2 を比較して等順序交換を行う必要があるため、時間計算量は O(n^2) になります。

平均すると、n*(n-1)/4 回のスワップ操作が必要です。比較操作はスワップ操作以上であり、複雑さの上限は O(n^2) であるため、平均的な場合の時間複雑さは O(n^2) です。

空間複雑性分析

バブルソートは隣接する要素間の交換操作に過ぎないため、一定量の余分なスペースしか使用せず、空間計算量はO(1)である。

安定性分析

では、バブル ソートは安定しているのでしょうか? もちろん安定しています。私たちのコードでは、nums[j] > nums[j + 1] の場合、交換されます。等しい場合は、交換されません。等しい要素の相対的な位置は変わらないので、バブル ソートは安定しています。

単純な選択ソート

バブルソートは、継続的に交換を行い、交換を通じて最終的なソートを完了します。 単純な選択ソートの考え方も理解しやすいです。 主な考え方は、下の図に示すように、n-i+1 個のレコードから最小のキーワードを持つレコードを、順序付けられたシーケンスの i 番目のレコードとして毎回選択することです。

たとえば、上の図では、緑はソートされた要素を表し、赤はソートされていない要素を表します。現在のポインタは 4 を指しているので、赤い要素を走査して最小値を見つけ、それを 4 と交換します。選択ソートでは、1 サイクル実行後、少なくとも 1 つの要素を元の位置に戻すことができることがわかりました。

コードの実行プロセスを見てみましょう。これを読めば、きっとコードが書けるようになります。

注: 理解しやすくするために、最小値はインデックスではなく値を保存します。実際のコードではインデックスを保存します。

シンプルな選択ソートコード

クラスソリューション{
公共  int [] sortArray( int [] 数値) { 
 
 int len ​​= nums.length;
整数 最小= 0;
 ( int i = 0; i < len; ++i)の場合{
最小値= i;
            // 最小値を見つけるために横断する
( int j = i + 1; j < len; ++j)の場合{
                nums[ min ] > nums[j] の場合、 min = j;
            }
            min != i の場合、 swap(nums,i, min );
        }
数値を返します。
    }
パブリックvoid swap ( int [] 数値、 int i、 int j) {
整数  temp = 数値[i];
        数値[i] = 数値[j];
        数値[j] = temp ;
    }
 }

時間計算量分析

単純選択ソートのプロセスから、その最大の特徴は、要素の交換と移動の回数が非常に少ないため、ソート時間が節約されることです。単純選択はバブルソートとは異なります。最良の場合でも最悪の場合でも、要素間の比較回数は同じであることがわかりました。i 番目のソートには n - i 回の比較が必要で、n は要素の数を表し、合計で (n-1) + (n-2) +.... + 2 + 1 = n*(n-1)/2 回の比較が必要です。

スワッピングの場合、最良のケースは 0 回のスワップであり、最悪のケース (順序が逆の場合) は n - 1 回のスワップです。すると、単純選択ソートの時間計算量も O(n^2) になりますが、スワップの数はバブルソートよりもはるかに少ないため、効率はバブルソートよりも優れています。

空間複雑性分析

アニメーションからわかるように、単純な選択ソートでは一定量の余分なスペースしか使用されないため、スペースの複雑さは O(1) です。

安定性分析

考えてみましょう。単純な選択ソートは安定していますか?

明らかにこれは安定していません。ポインターの背後にある最小値を見つけて、それをポインターが指す値と交換する必要があるためです。下の図を参照してください。

この時点で、次の要素から最小の要素を見つけて、それをポインターが指す要素 (要素 2) と交換する必要があります。しかし、それらを交換した後、2 つの等しい要素 3 の相対的な位置が変わったため、単純選択ソートは不安定なソート アルゴリズムであることがわかりました。

この記事はWeChatの公開アカウント「Yuan Chu's Algorithm House」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合は、Yuan Chu の Algorithm House 公開アカウントにご連絡ください。