Javaでの選択ソート
1. 序章
このチュートリアルでは、選択ソートを学習し、Javaでその実装を確認し、そのパフォーマンスを分析します。
2. アルゴリズムの概要
選択ソートは、ソートされていない配列の1番目の位置にある要素から始まり、後続の要素をスキャンして最小の要素を見つけます。 見つかったら、最小の要素が1 stの位置にある要素と交換されます。
次に、アルゴリズムは2 nd の位置にある要素に移動し、後続の要素をスキャンして、2 ndの最小要素のインデックスを見つけます。 見つかったら、2番目に小さい要素が2 ndの位置にある要素と交換されます。
このプロセスは、配列のn-1 th 要素に到達するまで続きます。これにより、n-1 thの最小要素がn-1thに配置されます。位置。 最後の要素は、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の配列をソートするために必要な比較の数を示します。
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の完全なコードを確認してください。