java-selection-sort
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で]。