Javaでの選択ソート

1. 前書き

2. アルゴリズムの概要

選択ソートは、ソートされていない配列の1 ^ st ^位置にある要素で始まり、後続の要素をスキャンして*最小の要素を見つけます*。 見つかったら、最小要素が1 ^ st ^位置の要素と交換されます。
次に、アルゴリズムは2番目の位置の要素に移動し、後続の要素をスキャンして、最小の2番目の要素のインデックスを見つけます。 見つかったら、2番目に小さい要素が2 ^ nd ^位置の要素と交換されます。
このプロセスは、配列のn-1 ^ th ^要素に達するまで続き、n-1 ^ th ^の最小要素をn-1 ^ th ^の位置に配置します。 最後の要素は、n-1 ^ th ^反復で自動的に所定の位置に配置され、それによって配列がソートされます。
配列を降順でソートするには、*最小要素ではなく最大要素を見つけます*。
ソートされていない配列の例を見て、昇順でソートして、アルゴリズムを視覚的に理解しましょう。

2.1. 例

次の並べ替えられていない配列を検討してください。
_int [] arr = \ {} _
*繰り返し1 *
上記のアルゴリズムの動作を考慮して、1 ^ st ^の位置にある要素– 5 –から開始し、後続のすべての要素をスキャンして最小の要素– 1を見つけます。 次に、最小要素を1 ^ st ^位置の要素と交換します。
変更された配列は次のようになります。
_ \ {} _
行われた合計比較：4
*繰り返し2 *
2番目の反復では、2 ^ nd ^要素– 4 –に進み、後続の要素をスキャンして2番目に小さい要素– 2を見つけます。 次に、2番目に小さい要素を2 ^ nd ^位置の要素と交換します。
変更された配列は次のようになります。
_ \ {} _
行われた合計比較：3
同様に続けて、次の反復があります。
*イテレーション3 *
_ \ {} _
行われた合計比較：2
*イテレーション4 *
_ \ {} _
行われた合計比較：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;
        }
    }
}
そしてもう少しエルボグリースを使用して、link:/java-comparator-comparable[__Comparator__s]を使用してこれらを組み合わせることができます。

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

4.1. Time

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

4.2. スペース

5. 結論

選択ソートの完全なコードを確認してくださいhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで]。