Java選択ソート：ハウツーガイド

Java選択ソートは、リスト内の最小の項目を検索し、その値をリストの先頭に移動します。これは、最初のリストのすべての要素がソートされるまで繰り返し発生します。選択ソートは、ソートされたリストを返します。

Javaでリストをどのようにソートしますか？いくつかのオプションがあります。一般的なオプションの1つは、選択ソートです。

このガイドでは、選択の種類とその機能について説明します。また、Javaで選択ソートを作成する方法についても説明し、独自の選択ソートを作成する方法を理解できるようにします。始めましょう！

Java選択ソートとは何ですか？

選択ソートは、リスト内の最小アイテムを繰り返し検索し、リスト内のソートされていないアイテムの先頭に移動します。このプロセスは、リストが注文されるまで、リスト内のすべてのアイテムに対して繰り返されます。

リストの最初のアイテムは、最小のアイテムと見なされます。このアイテムは次の要素と比較されます。次の要素が小さい場合、要素は交換されます。このアルゴリズムは、最後の要素に到達するまで最小要素を見つけます。次に、プログラムは最小のアイテムをリストの先頭に移動します。

選択ソートでは、リストには、ソートされたリストとソートされていないリストの2つの部分が含まれます。要素が並べ替えられると、並べ替えられていないサブ配列から並べ替えられたサブ配列に移動します。

リストは昇順または降順で並べ替えることができます。

選択ソートはいつ使用する必要がありますか？

小さなリストを並べ替える必要がある場合は、選択並べ替えが最適です。これは、大きなリストを並べ替えるより効率的な方法があるためです。マージソート、挿入ソート、クイックソートなどのアルゴリズムは、Javaプログラミングの選択ソートよりも効率的です。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

配列のすべての要素をチェックすることが必須である場合、選択ソートが最適に機能します。これは、リスト内のアイテムがほとんどまたはまったくソートされていない場合に当てはまります。選択ソートは通常、理解しやすいバブルソートよりも優れています。

選択ソートはどのように機能しますか？

アルゴリズムに何をさせたいのかを最初に知らずに、Javaでアルゴリズムを実装しようとしても意味がありません。まず、選択ソートでリストを順番に並べ替える手順を説明します。

次のソートされていない配列について考えてみます。

17

14

9

12

選択ソートは、最初の項目をリストの最小のものとして設定します。これは一時的な値であり、プログラムが比較するたびに変化します。この値は独自の変数に格納されます。

最小=17
17	14	9	12

「最小」項目は、2番目の要素と比較されます。この要素は、配列のソートされていない部分にあります。ソートされた要素の後のすべての要素はソートされていません。

2番目の要素が「最小」アイテムよりも小さいとします。この場合、「最小」項目の値は2番目の項目の値に設定されます。 14は17より小さいため、新しい最小値は14になります。

最小=14
17	14	9	12

このプロセスは、リスト内のアイテムごとに繰り返されます。 9は14未満です。したがって、「最小」の値は9になります。9は12以上であるため、最小の値は同じままです。

1回の反復の後、リストでは9が最小の数であることがわかりました。このアイテムはリストの先頭に移動されます：

9

17

14

12

このプロセスは、最初のソートされていない要素から最初からやり直します。したがって、次の一連の比較は17から始まります：

• 17は最小値と同じです。
• 私たちのプログラムは17と14を比較します。「最小」の値は14になります。
• 私たちのプログラムでは、14と12を比較しています。「最小」の値は12になります。
• 私たちのプログラムは、リスト内のソートされたアイテムの最後に12を移動します。

リストは次のようになります：

9

12

17

14

このプロセスは、リストが注文されるまで繰り返されます。アルゴリズムの実行が終了すると、次のリストが返されます。

9

12

14

17

リストは昇順で並べ替えられています。

Javaで選択ソートを作成する方法

選択ソートがどのように機能するかを知ることは1つのことです。構築するのは別です。ウォークスルーで説明したロジックを使用して、Javaで選択ソートをコーディングしましょう。

プログラムの設定

selection_sort.javaというファイルを作成します。まず、Java配列ライブラリをコードにインポートします。

import java.util.Arrays;

このライブラリは、コードの後半で使用します。これを使用して、ソートされた配列を文字列に変換し、コンソールに出力できるようにします。

ソート関数を作成する

次に、クラスを宣言し、選択ソートを実行するメソッドを作成します。 selection_sort.javaに以下を追加します ファイル：

class SelectionSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			int minimum = item;
			for (int number = minimum + 1; number < size; number++) {
				if (array[number] < array[minimum]) {
					minimum = number;
				}
			}
			
			int temporary = array[item];
			array[item] = array[minimum];
			array[minimum] = temporary;
		}
	}
}

このクラスでは、 sortNumbersというメソッドを定義しました。 これは私たちのソートを実行します。配列の長さを計算することから始めます。配列の長さをJava変数に格納します。

次に、Javaforループを作成します。このループは、リスト内のすべてのアイテムを繰り返し処理します。このforループ内で、リストの最初のアイテムである最小アイテムが見つかります。

次に、別のforループを開始して、最小アイテムをリスト内のすべてのアイテムと比較します。

forループが読み取っている数値が最小数値よりも小さい場合、「最小」の値がその数値になります。ループでは、「数値」は、最小値と比較している数値のインデックス値を表します。

最小数がリスト内のすべての数と比較されると、内側のforループが停止します。次に、リスト内のすべてのソートされた番号の後に最小番号が移動されます。

ソート関数を呼び出す

私たちのコードはまだ何もしていません。クラスをまだ呼び出しておらず、並べ替えるリストを提供していません。

sortNumbersの下 リスト内のメソッドに、次のコードを追加します：

public static void main(String args[]) {
	int[] toSort = { 17, 14, 9, 12 };
	SelectionSort newSort = new SelectionSort();
	newSort.sortNumbers(toSort);
	
	System.out.println(Arrays.toString(toSort));
}

mainメソッド内で、 toSortと呼ばれる並べ替えるアイテムのリストを宣言しました。 。次に、newSortというSelectionSortクラスのインスタンスを初期化します。これを使用して、 sortNumbersを呼び出します。 toSort配列の値をソートするメソッド。

sortNumbersメソッドが実行された後、ソートされた配列をコンソールに出力します。これは、 Arrays.toString（）を使用して行います。 配列を文字列のリストに変換するメソッド。

コードを実行してみましょう：

[9, 12, 14, 17]

リストが並べ替えられました！

選択ソートJava：値を降順でソート

値を降順で並べ替えることができることに注意してください。これを行うには、 sortNumbersの次のコード行を置き換えます。 方法：

if (array[number] < array[minimum]) {

このコードで：

if (array[number] > array[minimum]) {

このコードは、「最小」値がforループによってアクセスされている値よりも大きいかどうかをチェックします。これは、「最小」の値が、最小値ではなく、リスト内の最大値を反映することを意味します。

混乱を避けるために、リストを降順で並べ替える場合は、「minimum」の名前を「maximum」に変更する必要があります。

あなたはそれをしました。選択ソートアルゴリズムを使用して、Javaでリストをソートしました。

Java選択ソートの複雑さは何ですか？

アルゴリズムを評価する際に考慮する必要のある時間計算量は、最良の場合、最悪の場合、平均の場合の3つです。

選択ソートには、O（n ^ 2）の最良、平均、および最悪の場合の複雑さがあります。これは、リスト内のアイテムの数が増えるにつれて、アルゴリズムに指数関数的に時間がかかることを意味します。

アルゴリズムの複雑さに混乱していませんか？ BigONotationに関する2部構成のシリーズをご覧ください。これは、アルゴリズムの複雑さを説明するために使用する表記法です。

結論

選択ソートは、データのリストをソートする効率的な方法です。それらは、ソートされていないリストから最小のアイテムを選択し、そのアイテムをソートされていないリストの先頭に移動することによって機能します。このプロセスは、リストが並べ替えられるまで繰り返されます。

Java開発者になりたいですか？ Javaの学習方法ガイドをご覧ください。このガイドには、最高のオンラインコースと学習リソースに関する最高の学習のヒントとアドバイスがあります。