一目でわかるアルゴリズム「選択ソート」

「選択ソート」は実際の応用では「挿入ソート」ほど広範囲ではありませんが、ソートアルゴリズムの研究には欠かせないものでもあります。バブルソートと挿入ソートはどちらも、2 つのネストされたループ内の要素をゆっくりと比較し、要素の位置を継続的に調整します。「選択ソート」はより直接的です。移動しない場合は何もする必要はありません。ただし、移動を行った後は、対応する要素が所定の位置に配置されている必要があり、要素の位置は変更されません。

[[320109]]

そのロジックを詳しく見てみましょう。

1. 選択ソートとは何ですか?

選択ソートも非常に単純なソートアルゴリズムです。ソートするデータのセットを 2 つのセグメントに分割し、1 つは「ソート済み」データ、もう 1 つは「ソートされていない」データにします。もちろん、最初は「ソート済み」セクションにデータはありません。ソートが開始されると、そのたびに「ソートされていない」データから最小の要素が取り出され（ここで最小の要素が取り出される点が「挿入ソート」と異なることに注意してください）、この最小の要素が「ソートされた」データの最後の要素の後に挿入されます（ここで実際に最小の要素は「ソートされた」データの末尾の次の要素と交換されます）。これにより、「ソートされた」データは常に順序付けされます。このプロセスは、すべての「未ソート」データが交換され、ソート全体が完了するまでループで繰り返されます。

以下に図付きの例を示します。

（インターネットからの写真）

上の図からわかるように、初期配列は

要素	29	72	98	13	87	66	52	51	36
添字	0	1	2	3	4	5	6	7	8

この配列を小さいものから大きいものの順に並べ替えるには、デフォルトの初期状態は完全に順序付けられていないため、この配列を走査して最小の要素を見つけ始めます。

1. 最初の大きなループで、配列全体で最小の要素「13」を見つけ、この最小の要素「13」を配列の先頭の要素「29」と交換します。スワップ後の配列は次のようになります。

要素	13	72	98	29	87	66	52	51	36
添字	0	1	2	3	4	5	6	7	8

2. 2 番目の大きなループでは、要素「13」は「ソート済み」セグメントに属し、残りのすべての要素は「未ソート」セグメントに属します。残りの要素から最小の要素「29」を見つけ、この最小の要素「29」を要素「72」と交換します (要素「72」はソートされた配列の次の要素であるため)。交換後の配列は次のようになります。

要素	13	29	98	72	87	66	52	51	36
添字	0	1	2	3	4	5	6	7	8

3. 3 番目の大きなループでは、要素「13」と「29」がすでに「ソート済み」セクションに存在し、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「36」を見つけ、この最小の要素「36」を要素「98」と交換します (要素「98」はソートされた配列の次の要素であるため)。交換後の配列は次のようになります。

要素	13	29	36	72	87	66	52	51	98
添字	0	1	2	3	4	5	6	7	8

4. 4 番目の大きなループでは、すでに「ソート済み」セクションに要素「13」、「29」、「36」が存在し、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「51」を見つけ、この最小の要素「51」を要素「72」と交換します (要素「72」はソートされた配列の次の要素であるため)。交換後の配列は次のようになります。

要素	13	29	36	51	87	66	52	72	98
添字	0	1	2	3	4	5	6	7	8

5. 5 番目の大きなループでは、すでに「ソート済み」セクションに要素「13」、「29」、「36」、および「51」が存在し、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「52」を見つけ、この最小の要素「52」を要素「87」と交換します (要素「87」はソートされた配列の次の要素であるため)。交換後の配列は次のようになります。

要素	13	29	36	51	52	66	87	72	98
添字	0	1	2	3	4	5	6	7	8

6. 6 番目の大きなループでは、「ソート済み」セクションにすでに要素「13」、「29」、「36」、「51」、「52」があり、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「66」を見つけ、この最小の要素「66」がすでにソートされた配列の次の要素であることがわかります。そのため、これを交換する必要はなく、配列は変更されません。

要素	13	29	36	51	52	66	87	72	98
添字	0	1	2	3	4	5	6	7	8

7. 7 番目の大きなループでは、すでに「ソート済み」セクションに要素「13」、「29」、「36」、「51」、「52」、および「66」が存在し、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「72」を見つけ、この最小の要素「72」を要素「87」と交換します (要素「87」はソートされた配列の次の要素であるため)。交換後の配列は次のようになります。

要素	13	29	36	51	52	66	72	87	98
添字	0	1	2	3	4	5	6	7	8

8. 8 番目の大きなループでは、「ソート済み」セクションにすでに要素「13」、「29」、「36」、「51」、「52」、「66」、および「72」があり、残りの要素はすべて「未ソート」です。残りの要素から最小の要素「87」を見つけ、この最小の要素「87」がすでにソートされた配列の次の要素であることがわかります。そのため、これを交換する必要はなく、配列は変更されません。

要素	13	29	36	51	52	66	72	87	98
添字	0	1	2	3	4	5	6	7	8

9. 9 番目の大きなループでは、すでに「ソート済み」セクションに要素「13」、「29」、「36」、「51」、「52」、「66」、「72」、「87」があります。残っているソートされていない要素は「98」だけです。その位置は変更しないでください。つまり、この時点ですべてのソートが完了し、配列の最終状態は次のようになります。

要素	13	29	36	51	52	66	72	87	98
添字	0	1	2	3	4	5	6	7	8

選択ソートのコード図を見てみましょう。

アルゴリズムの質問: 配列 arr を小さいものから大きいものの順に並べ替えます。配列 arr は空ではなく、arr の長さは n であると仮定します。アイデア: 選択ソート法を使用する

パブリックvoid 選択ソート ( int [] arr) {
整数i,j;
 int n = arr.length; 
     
    //各大きなループは残りの要素の最小値を見つけることができます
(i=0; i<n; i++)の場合{
        // min変数は最小値のインデックスを格納するために使用されます。最初は、位置iが最小値であると仮定して、iは最初にminに割り当てられます。  
整数 最小値= i;
        //サブループは、i の最後の桁から始めて、その後ろのすべての要素を走査してサイズを比較するために使用されます。
 (j=i+1; j<n; j++)の場合{
            //最小ビットの値より小さい要素がある場合、この要素の添え字を最小に代入します 
            もしarr[j] < arr[ min ]であれば
最小値= j;
            }
        }
        // minがiと等しくない場合は、サブループで最小値が見つかったことを意味し、要素の位置を交換する必要があります。
        もしも(最小値!= i) {
            // swap メソッドは、配列内の 2 つの位置 (渡された配列と添え字) の値を交換するために使用されます。 swap メソッドは省略されています。
            swap(arr, min , i);
        }
    }
 }

2. 「選択ソート」のパフォーマンスはどの程度ですか?

前回の記事で説明したソートアルゴリズムの評価方法を使用して、「選択ソート」のパフォーマンス評価を実行します。

時間の計算量:

選択ソートの原理は、2 つのネストされたループで比較と交換を行うことです。したがって、簡単に言えば、その時間計算量は一般に O(n*n) です。しかし、注意深く分析する場合には、具体的なデータに注目する必要があります。しかし、データの状況がどうであろうと、要素比較の数は同じなので、最良のケースでも最悪のケースでも、要素比較の数は同じです。次に要素交換の回数を見てみましょう。ソートするデータがすでに順序付けられている場合は、要素交換はまったく必要ないので、交換回数は 0 です。ただし、ソートするデータがすべて逆順になっている場合は、n-1 回の要素交換が必要になります。

したがって、最良、最悪、平均の選択ソートの時間計算量は O(n*n) です。

空間の複雑さ:

選択ソートは、データの比較と交換が中心です。比較する要素の添え字を格納するための補助スペースのみが必要で、追加のスペースは消費しません。したがって、その空間計算量は O(1) です。

ソート安定性:

選択ソートアルゴリズムは安定したソートアルゴリズムではありません。安定性ソートの別の説明は次のとおりです。ソートの前後で 2 つの等しい要素の相対的な位置は一定のままです。

選択ソートが安定性ソートではないのはなぜでしょうか? たとえば、配列 6、7、6、2、8 では、最初にループされると、最初の位置にある 6 が、その後ろの 2 と入れ替わります。この時点で、2 つの 6 の相対的な前後の位置が変更されています。したがって、選択ソートは安定したソートアルゴリズムではありません。