Java での選択の並べ替え

Java の選択ソートは、ソートされていない部分から最小の要素を継続的に見つけて先頭に保持するソート方法です (昇順でソートする場合)。このプロセスは、入力配列がソートされるまで繰り返されます。また、選択ソートでは、入力配列を 2 つのサブ配列に分割します。1 つの配列はソートされた要素に使用され、もう 1 つの配列はソートされていない要素に使用されます。最初は、ソートされた部分配列には要素がありません。次のセクションで選択ソートの仕組みを詳しく見てみましょう。

Java での選択ソートの仕組み

選択ソートは、入力配列から 2 つの部分配列を保持するという単純な方法で機能します。それらは次のとおりです:

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

• ソートされた要素を保持するためのソートされたサブ配列
• 未ソートの要素を保持する未ソートの部分配列。

アルゴリズム

以下は選択ソートに使用されるアルゴリズムです

1. 最小 (MIN) ポインタを位置 0 に設定します。
2. 配列内の要素のリストから最小の要素を見つけます

• 最小要素を位置 0 と交換します

1. MIN ポインタを次の位置に移動します
2. 入力配列がソートされるまでプロセスを繰り返します。

例を使って選択ソートを理解しましょう。以下は、ソートする必要がある入力配列です。太字の青色の要素は、並べ替えられた配列の一部になります。

ステップ 1: MIN ポインタを最初の位置に設定します。したがって、MIN ポインタは 15 を指します。

最小: = 15

ステップ 2: 残りの要素と比較して最小の要素を見つけます。 15 と 21 を比較すると、15 が最小です。したがって、この場合、最小値は変更されません。

最小: = 15

15 と 6 を比較すると、6 が最小です。

最小: = 6

6 と 3 を比較すると、3 が最小です。

最小: = 3

19 は 3 より大きいため、この場合も 3 は小さくなります。

最小: = 3

最小: = 3

最後に、この反復で 3 が最小であることがわかります。

ステップ 3: 最小の要素を位置 0 の要素と交換します。

ステップ 4: MIN ポインタを次の位置にインクリメントします。

ステップ 5: 残りの要素と比較して、次に小さい要素を見つけます。

最小: = 21

最小: = 6

最小: = 6

最小: = 6

最小: = 6

ステップ 6: 最小の要素を位置 1 の要素と交換します。

以下に示すように、ソートされた配列が形成されるまでこのプロセスを繰り返します。

Java で選択ソートを実装する例

すでに上で述べたように、選択の並べ替えは最小値の検索と交換に基づいています。ここで、Java を使用して選択ソートを実装する方法を見てみましょう。

選択ソートを使用して配列内の要素を並べ替える Java プログラム

コード:

import java.util.*;
public class SelSortExample {
//Method that implements Selectionsort
public static void selsort(int[] arr)
{
int n=arr.length; //length of the array
for(int i=0;i<n-1;i++)
{
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j<n;j++)
{
System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]);
if(arr[j]<arr[MIN])
{
System.out.println(arr[MIN] + " is greater than " + arr[j] );
MIN=j;
}
}
//Swap the smallest element with element in MIN position
int temp=arr[i];
arr[i]=arr[MIN];
arr[MIN]=temp;
}
}
public static void main(String[] args) {
int[] arr= {15,21,6,3,19,20}; // input array
System.out.println("Elements in the array before Sorting: "+ Arrays.<em>toString</em>(arr));
<em>selsort</em>(arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays.<em>toString</em>(arr));
}
}

サンプル出力:

上記のプログラムには、main メソッドと sell sort メソッドという 2 つのメソッドがあります。 main メソッドは、入力配列を引数として渡して sell sort メソッドを呼び出します。最小要素が識別され、MIN が指す要素と交換されます。

The selection sort can also be used where the input array is not defined in code. Let us see how it works using the below program.

Java Program to Sort the Elements using Selection Sort

Code:

import java.util.*;
public class SelectionSortExample
{
public static void main(String args[])
{
int n, i, j, tempvar;
Scanner <u>sc</u> = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array[] = new int[n]; //<u>initialising</u> the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i<n; i++)
{
array[i] = sc.nextInt();
}
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(array[i] > array[j])
{
tempvar = array[i];
array[i] = array[j];
array[j] = tempvar;
}
}
}
System.out.print("Array after Sorting is :\n");
for(i=0; i<n; i++)
{
System.out.print(array[i]+ " ");
}
}
}

Sample Output:

Here, the input elements given by the user will be compared with the temporary variable and swapped. The process will be repeated until a sorted array is formed.

Performance of Selection Sort

This sorting technique is used for its simplicity and certain other performance advantages over other more sorting techniques.

Conclusion

The selection sort does not work efficiently on large lists as it consumes more time for comparison. Selection sort is a method in which an input array will be divided into two subarrays in order to keep them sorted and unsorted elements. The minimum element in the array will be swapped with the element in the first position, and the process continues until a sorted array is formed.

以上がJava での選択の並べ替えの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。