Javaでの選択ソート

投稿日: 2019-10-18 2022-10-25
タグ: Algorithms, Java

1. 序章

このチュートリアルでは、選択ソートを学習し、Javaでその実装を確認し、そのパフォーマンスを分析します。

2. アルゴリズムの概要

選択ソートは、ソートされていない配列の1番目の位置にある要素から始まり、後続の要素をスキャンして最小の要素を見つけます。見つかったら、最小の要素が1 ^stの位置にある要素と交換されます。

次に、アルゴリズムは2 ^ndの位置にある要素に移動し、後続の要素をスキャンして、2 ^ndの最小要素のインデックスを見つけます。見つかったら、2番目に小さい要素が2 ^ndの位置にある要素と交換されます。

このプロセスは、配列のn-1 ^th要素に到達するまで続きます。これにより、n-1 ^thの最小要素がn-1^thに配置されます。位置。最後の要素は、n-1 ^thの反復で自動的に配置され、配列が並べ替えられます。

配列を降順で並べ替えるために、最小の要素ではなく最大の要素を見つけます。

ソートされていない配列の例を見て、アルゴリズムを視覚的に理解するために昇順でソートしてみましょう。

2.1. 例

次のソートされていない配列について考えてみます。

int [] arr = { 5、4、1、6、2 }

反復1

上記のアルゴリズムの動作を考慮して、1 ^stの位置– 5 –の要素から開始し、後続のすべての要素をスキャンして最小の要素–1を見つけます。次に、最小の要素を1 ^stの位置にある要素と交換します。

変更された配列は次のようになります。

{ 1、4、5、6、2 }

行われた合計比較：4

反復2

2番目の反復では、2 ^nd要素– 4 –に移動し、後続の要素をスキャンして2番目に小さい要素–2を見つけます。次に、2番目に小さい要素を2 ^ndの位置にある要素と交換します。

変更された配列は次のようになります。

{ 1、2、5、6、4 }

行われた合計比較：3

同様に続けると、次の反復があります。

反復3

{ 1、2、4、6、5 }

行われた合計比較：2

反復4

{ 1、2、4、5、6 }

行われた合計比較：1

3. 実装

いくつかのforループを使用して選択ソートを実装しましょう。

public static void sortAscending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minElementIndex] > arr[j]) {
                minElementIndex = j;
            }
        }

        if (minElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minElementIndex];
            arr[minElementIndex] = temp;
        }
    }
}

もちろん、それを逆にするために、私たちは非常に似たようなことをすることができます：

public static void sortDescending(final int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int maxElementIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[maxElementIndex] < arr[j]) {
                maxElementIndex = j;
            }
        }

        if (maxElementIndex != i) {
            int temp = arr[i];
            arr[i] = arr[maxElementIndex];
            arr[maxElementIndex] = temp;
        }
    }
}

そして、もう少しエルボーグリースを使用すると、コンパレータを使用してこれらを組み合わせることができます。

4. パフォーマンスの概要

4.1. 時間

前に見た例では、最小の要素を選択するには、合計（n-1）の比較が必要であり、その後、1 ^stの位置にスワップします。同様に、次に小さい要素を選択するには、合計（n-2）の比較が必要であり、続いて2 ^ndの位置にスワップします。

したがって、インデックス0から開始して、 n-1、n-2、n-3、n-4…。 1 比較。最後の要素は、前の反復とスワップのために自動的に配置されます。

数学的には、最初のn-1個の自然数の合計は、選択ソートを使用してサイズnの配列をソートするために必要な比較の数を示します。

n自然数の合計の式は次のとおりです。 n（n + 1）/2。

この場合、最初のn-1自然数の合計が必要です。したがって、上記の式でnをn-1に置き換えて次のようにします。

（n-1）（n-1 + 1）/ 2 =（n-1）n / 2 = （n ^ 2-n）/ 2

n ^ 2 は、 n の成長に伴って顕著に成長するため、 n のより高いパワーをパフォーマンスベンチマークと見なし、このアルゴリズムの時間計算量をにします。 O（n ^ 2）。の

4.2. スペース

補助スペースの複雑さの観点から、選択ソートでは、スワッピングのために値を一時的に保持するために1つの追加変数が必要です。したがって、選択ソートのスペースの複雑さはO（1）です。

5. 結論

選択ソートは、理解して実装するための非常に単純なソートアルゴリズムです。残念ながら、その2次時間計算量は、高価なソート手法になります。また、アルゴリズムは各要素をスキャンする必要があるため、最良の場合、平均的な場合、および最悪の場合の時間計算量は同じです。

挿入ソートやシェルソートのような他のソート手法も、2次の最悪の場合の時間計算量を持ちますが、最良の場合と平均的な場合の方がパフォーマンスが優れています。

GitHubでSelectionSortの完全なコードを確認してください。

getdocs

13036