選択ソート Java 例題付きプログラム

選択並べ替えはどのように機能しますか?

選択ソートは、次のような単純なソート アルゴリズムを実装します。

• アルゴリズムは最下位の要素を繰り返し検索します。
• 現在の要素を最も低い値を持つ要素と交換します
• 選択ソートの反復/パスごとに、要素が交換されます。

したがって、すべてのパスは 配列 データは2つの領域に分けられます。1つは左側から拡大するソート済みのブロック、もう1つは右側に向かって縮小するソートされていないブロックです。アルゴリズムはソートされていないブロックを走査し、そこで見つかった最小値のインデックスを記憶し、その値をソートされていないブロックの最初の位置の値と交換します。

1回のパスで交換が1回しか行われないため、n個の要素を持つ配列は最大でn-1回の交換後に順序付けられます。この特性が、このルーチンを他の初心者レベルのルーチンと区別する点です。 Java ソートアルゴリズムは、データをはるかに頻繁に移動させる。

その trac以下のeは、次のセクションのプログラムが実行時に出力するサンプル配列{860, 8, 200, 9}と全く同じです。

その詳細が2つあります trac注目すべき点がいくつかあります。まず、パス3では、順序は変わりませんが、スワップが発生したと報告されます。これは、残りの最小値が既に現在のインデックスにあり、プログラムがその要素を自身と交換しているためです。次に、比較回数はパスごとに1つずつ減少します（3回、次に2回、次に1回）。これは、このページの下部にある計算量の数値の背後にあるパターンです。

Java 選択ソートを実装するプログラム

以下のクラスは SelectionSortAlgo という名前で、com.guru99 パッケージに属しています。main() メソッドはサンプル配列を宣言し、表示し、ソートのために selection() メソッドに渡し、再度表示します。ヘルパー関数 printArray() はすべての要素を 1 行に書き込むため、読みやすいパスごとのログが生成されます。

selection() 関数内では、外側のループがソート済み領域と未ソート領域の境界を示し、変数 index にはこれまでに見つかった最小値の位置が保持され、各パスの最後にある 3 つの代入によってスワップが実行されます。

package com.guru99;
 
public class SelectionSortAlgo {
 
	public static void main(String a[])
	{  
		int[] myArray = {860,8,200,9}; 
		
		System.out.println("------Before Selection Sort-----");
 
		printArray(myArray);
 
 
		selection(myArray);//sorting array using selection sort  
 
		System.out.println("-----After Selection Sort-----");  
 
		printArray(myArray); 
	} 
	
		public static void selection(int[] array)
	{  
		for (int i = 0; i < array.length - 1; i++)  
		{  System.out.println("Sort Pass Number "+(i+1));
			int index = i;  
			for (int j = i + 1; j < array.length; j++)
			{   
			    System.out.println("Comparing "+ array[index]  + " and " + array[j]);  
				if (array[j] < array[index]){ 
				System.out.println(array[index]  + " is greater than " + array[j] );
					index = j;
				
				
				}  
			}  
 
			int smallerNumber = array[index];   
			array[index] = array[i];  
			array[i] = smallerNumber;  
			System.out.println("Swapping Elements: New Array After Swap");
			printArray(array);
		}  
	}  
	static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
 
}

出力：

クラスをコンパイルして実行すると、以下のコンソールログが生成されます。各パスごとに1つの出力ブロックが表示されます。

------Before Selection Sort-----
860 8 200 9 
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Comparing 8 and 200
Comparing 8 and 9
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 860 and 200
860 is greater than 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860 
Sort Pass Number 3
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 9 200 860 
-----After Selection Sort-----
8 9 200 860

初心者がこの例を初めて実行する際に、2つの問題に遭遇します。ファイルには次のように宣言されています。 package com.guru99;ソースは一致する場所に存在する必要があります com/guru99 ディレクトリを指定しないと、コンパイラはパッケージ名またはクラス名の不一致を報告します。クラスは完全修飾名で起動する必要があります。 java com.guru99.SelectionSortAlgoなぜなら、 java SelectionSortAlgo NoClassDefFoundError が発生します。

ループの境界もよくある落とし穴です。外側のループはここで停止します。 array.length - 1 そして内側のループは i + 1境界を変更すると、余分な空のパスが発生するか、ArrayIndexOutOfBoundsException が発生します。

選択ソートの時間計算量と空間計算量

プログラムの内部ループは常に配列の末尾まで実行されるため、アルゴリズムはデータの形状に関係なく同じ数の比較を実行します。n個の要素を持つ配列の場合、その合計はn(n-1)/2となり、4つの要素を持つサンプルでは6になります。そして、上記の出力では実際に6行の比較処理が行われます。

その均一な数字の並びから、３つの結果が導き出される。

• 選択ソートは適応的ではない。ソートされた入力は逆順の入力と全く同じコストがかかるため、早期終了ショートカットのようなものはない。 バブルソート オファー。
• 交換回数の少なさがこのアルゴリズムの強みです。交換回数は最大でもn-1回で済み、他の単純なソートアルゴリズムが行う2乗個の移動回数に比べてはるかに少ない回数です。
• メモリ使用量は一定です。ループカウンタと、一時変数 index および smallerNumber の 2 つだけが必要なので、補助メモリは O(1) で済み、ソートはインプレースで行われます。

2次関数的な増加は実際的な限界です。配列のサイズを2倍にすると比較処理は約4倍になるため、選択ソートは、O(n log n)アルゴリズムが適切な選択肢となる実運用データセットよりも、教育、小規模な配列、組み込みコードに適しています。

選択ソートの利点と欠点

アルゴリズムが役立つ場面と害になる場面を理解することで、いつアルゴリズムを使うのが適切かを判断しやすくなる。

優位性

• ロジックは短く読みやすいので、標準的な最初のソート演習として、 挿入ソート.
• ソートはインプレースで行われるため、2つ目の配列が割り当てられることはなく、メモリ使用量は入力データ量に応じて増加しません。
• アレイへの書き込み回数は最大でn-1回に抑えられるため、書き込み速度が遅かったり、書き込みによって媒体が摩耗したりするストレージにおいては重要な意味を持つ。
• 比較回数は配列の長さにのみ依存するため、実行時間は完全に予測可能です。

デメリット

• どのケースもO(n²)なので、このアルゴリズムは大規模なコレクションには対応できません。
• 既にソート済みの配列を検出できないため、処理が早期に終了することはありません。
• 上記に示した古典的な形式は不安定であるため、2つの等しい値が逆の順序になる可能性がある。
• ほぼ順序付けられたデータに対しては、挿入ソートよりも頻繁に比較が行われる。挿入ソートは線形時間に近い処理時間となる。

要するに、配列が小さく、書き込み処理のコストが高い場合は選択ソートを選択し、データセットが大きい場合や既にソートに近い状態にある場合は選択ソートを避けるべきです。

選択ソート対 Bubblソートと挿入ソートの比較

これら3つのアルゴリズムはすべて、2次計算量のインプレース比較ソートであるが、入力の形状が変わると動作が異なる。

この表は、よくある面接での回答を説明しています。選択ソートは交換回数の点で優れており、バブルソートは既に順序付けされている入力を認識する点で優れています。また、挿入ソートは実際のデータが部分的にソートされていることが多いため、実際には3つの中で最も高速です。配列の要素数が数十個を超えると、マージソートやクイックソートには到底及びません。

よくあるご質問