Javaの選択ソート徹底解説：仕組みと実装方法を初心者向けにわかりやすく紹介

Javaの選択ソート（Selection Sort）は、リストの中から最小値を探し、その値をリストの先頭へ移動させるアルゴリズムです。この操作を繰り返すことで、すべての要素が並べ替えられ、最終的にソート済みのリストが返されます。

Javaでリストを並べ替えるには、いくつかの方法があります。その中でも定番として知られているのが「選択ソート」です。

この記事では、選択ソートの基本的な考え方や動作の流れを解説し、さらにJavaで実際に選択ソートを実装する手順まで丁寧に紹介します。自分でコードを書けるようになることを目指しましょう。それでは始めましょう！

Javaの選択ソートとは？

選択ソートは、リストの中から最小の要素を繰り返し見つけ、未ソート部分の先頭に移動させていくアルゴリズムです。この処理をリスト内の全要素に対して繰り返すことで、リスト全体が整列されます。

まず、リストの最初の要素を「最小値」として扱います。この要素を次の要素と比較し、次の要素の方が小さければ値を入れ替えます。この比較を最後の要素に到達するまで続け、その後、プログラムは見つけた最小値をリストの先頭へ移動させます。

選択ソートでは、リストは「ソート済みの部分」と「未ソートの部分」の2つの領域に分かれています。要素が整列されるたびに、未ソートの部分配列からソート済みの部分配列へと移動していくイメージです。

なお、昇順だけでなく降順での並べ替えにも対応できます。

選択ソートはどんなときに使うべき？

選択ソートが適しているのは、小さなリストを並べ替えたい場合です。大きなリストを扱う場合には、より効率的な手法が存在するためです。マージソート、挿入ソート、クイックソートなどのアルゴリズムは、Javaプログラミングにおいて選択ソートよりも高い効率を発揮します。

また、配列内のすべての要素を必ず確認する必要がある場面では、選択ソートは特に有効です。これは、リスト内の要素がほとんど、あるいはまったく整列されていないケースに当てはまります。理解しやすいアルゴリズムとして知られるバブルソートと比べても、選択ソートの方が一般的に高いパフォーマンスを発揮します。

選択ソートの仕組み

アルゴリズムを実装する前に、まず「何をさせたいのか」を正しく理解することが大切です。ここでは、選択ソートがリストを整列させるまでの一連の手順を順番に見ていきましょう。

次のような未ソートの配列を例に考えてみます。

17

14

9

12

選択ソートでは、最初の要素をリスト内の最小値として設定します。これは一時的な値であり、プログラムが比較を行うたびに更新されます。この値は専用の変数に格納されます。

minimum = 17
17	14	9	12

次に、「minimum」の値を2番目の要素と比較します。2番目の要素は配列の未ソート部分に属しており、ソート済みの要素より後ろにある要素はすべて未ソートとみなされます。

仮に2番目の要素が「minimum」より小さかった場合は、「minimum」の値がその要素の値に置き換えられます。この例では14は17より小さいため、新しい最小値は14になります。

minimum = 14
17	14	9	12

この処理をリスト内の各要素に対して繰り返します。9は14より小さいので「minimum」は9に更新され、12は9より大きいため「minimum」は9のまま変わりません。

1回目の走査が終わると、リスト内の最小値が9であることが判明します。この要素がリストの先頭へ移動します。

9

17

14

12

次に、同じ処理を最初の未ソート要素から再び開始します。今回の比較は17から始まります。

• 17は現在の最小値と等しい。
• 17と14を比較すると、「minimum」は14になる。
• 14と12を比較すると、「minimum」は12になる。
• 12がリスト内のソート済み要素の末尾へ移動する。

この時点でリストは次のようになります。

9

12

17

14

この処理をリストが完全に整列するまで繰り返します。アルゴリズムの実行が完了すると、最終的に次のリストが得られます。

9

12

14

17

これでリストが昇順にソートされました。

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

選択ソートの仕組みを理解することと、実際にコードを書くことは別物です。ここでは、前章で確認したロジックをもとに、Javaで選択ソートを実装してみましょう。

プログラムの準備

まず、selection_sort.javaという名前のファイルを作成します。冒頭でJavaのArraysライブラリをインポートしましょう。

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の変数に格納します。

続いて、Javaのforループを作成します。このループはリスト内のすべての要素を順番に処理します。ループの内部では、まずリストの最初の要素を最小値として設定します。

そのうえで、もう1つのforループを使い、最小値候補とリスト内の各要素を比較していきます。

ループが読み取っている数値が現在の最小値より小さい場合、「minimum」の値がその数値に更新されます。ループ内の「number」は、最小値と比較対象となる数値のインデックスを表しています。

最小値候補がリスト内のすべての数値と比較されると、内側の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という配列を宣言しています。その後、SelectionSortクラスのインスタンスとしてnewSortを初期化し、これを使ってsortNumbersメソッドを呼び出すことで、toSort配列内の値がソートされます。

sortNumbersメソッドの実行後、Arrays.toString()メソッドを使って配列を文字列のリストに変換し、ソート結果をコンソールに出力します。

それではコードを実行してみましょう。

[9, 12, 14, 17]

リストが正しくソートされました！

選択ソートで降順に並べ替える方法

選択ソートは降順の並べ替えにも対応できます。その場合は、sortNumbersメソッド内の次のコードを、

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

以下のように書き換えます。

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

このコードは、「minimum」の値がforループで参照している値より大きいかどうかを判定します。これにより、「minimum」変数はリスト内の最小値ではなく最大値を保持するようになります。

混乱を避けるため、降順でソートする場合は変数名を「minimum」から「maximum」に変更しておくとよいでしょう。

お疲れさまでした。これで、選択ソートのアルゴリズムを使ってJavaでリストを並べ替えることができました。

Javaの選択ソートの計算量

アルゴリズムを評価する際には、3つの時間計算量を考慮する必要があります。最良ケース、最悪ケース、そして平均ケースです。

選択ソートの計算量は、最良・平均・最悪のいずれの場合もO(n^2)です。これは、リスト内の要素数が増えるにつれて、処理時間が急激に長くなることを意味します。

アルゴリズムの計算量についてよくわからない方は、Big O記法に関する2部構成の解説シリーズもぜひ参考にしてください。Big O記法は、アルゴリズムの複雑さを表現するために使われる表記法です。

まとめ

選択ソートは、データのリストを効率的に並べ替える手法のひとつです。未ソートのリストから最小の要素を選び出し、未ソート部分の先頭へ移動させるという処理を、リスト全体が整列するまで繰り返します。

Java開発者を目指している方は、Java学習ガイドもあわせてチェックしてみてください。効果的な学習のコツや、おすすめのオンライン講座・学習リソースなど、役立つ情報を多数掲載しています。