Javaの挿入ソート入門：アルゴリズムの仕組みと実装方法をわかりやすく解説

挿入ソート（Insertion Sort）は、リスト内の各要素を一つずつ評価していくソートアルゴリズムです。ある要素がその前の要素より小さければ、2つの要素を入れ替えます。そうでなければ、要素はそのままの位置に留まり、次の要素との比較へ進みます。

コンピュータはリストの並べ替えが得意です。ループを使えば、リスト内のすべての要素を調べ、順序が整うまで入れ替えを繰り返すことができます。

プログラミングには、リストをソートするための標準的な手法がいくつか存在し、これらは「ソートアルゴリズム」と呼ばれます。ソートアルゴリズムは、リスト内の全要素を読み込み、あらかじめ決められた手順に従って並べ替えを行います。その中でも最もよく知られているものの一つが「挿入ソート」です。

この記事では、Javaで挿入ソートを実装する方法を解説します。具体的な例も交えながら、このアルゴリズムの背後にあるロジックを学んでいきましょう。

Javaの挿入ソートとは？

Javaの挿入ソートは、トランプゲームで手札を並べ替える作業によく似ています。挿入ソートはリスト内の各要素をチェックし、必要に応じて左側の要素と入れ替えます。入れ替えるかどうかは、その要素が前の要素より大きいか小さいかによって決まります。

少し想像してみてください。あなたが今、トランプゲームをプレイしている場面です。手札を整理するとき、あなたは何をしますか？

まず左端から見ていき、2枚目のカードが正しく並んでいるかを確認します。そのカードが1枚目より大きければ、そのままの位置に置きます。そうでなければ、一つ左の位置へ移動させます。

この操作を手札のすべてのカードに対して繰り返し、すべてのカードが正しい順序に並ぶまで続けます。これこそが、挿入ソートの基本的な考え方です。

挿入ソートはどんなときに使うべき？

挿入ソートは、ソート対象の要素数が少ない場合や、すでにほぼ整列済みのデータに対して特に有効です。

大量のデータを扱う場合は、マージソートなど、より効率的なアルゴリズムを選ぶべきです。そのため、常に挿入ソートを使えばよいというわけではありません。とはいえ、バブルソートや選択ソートと比べると、挿入ソートの方が効率的に要素を並べ替えられます。

また、挿入ソートはシンプルなソートアルゴリズムなので、初心者が学習するのに最適です。

挿入ソートの手順を具体例で確認

トランプのイメージだけでは捉えづらい部分もあるため、ここからはプログラミングの例で具体的に見ていきましょう。次のリストを例にします。

8

6

3

9

まず、最初の要素（8）はすでにソート済みであると仮定します。

次に、リストの2番目の要素を最初の要素と比較します。もし最初の要素の方が大きければ、2番目の要素を先頭側へ移動させます。

この例では、6は8より小さいため、6を一つ前に移動し、8を一つ後ろへ移動します。

6

8

3

9

続いて、3番目の要素（3）を左側の要素と比較します。3は8より小さいでしょうか？ はい、小さいので8を右へ移動します。

6

3

8

9

では、3は6より小さいでしょうか？ これも小さいので、6を移動します。

3

6

8

9

最後に、4番目の要素（9）が他のすべての要素より大きいかどうかを確認します。この場合、9はそれより前の要素（8、6、3）のどれよりも大きいため、移動は不要です。

以上が、今回リストをソートするために使用したアルゴリズムの手順です。

• 最初の要素はソート済みとみなす。
• 2番目の要素を、その左側の要素と比較する。
• その要素が左側の値より大きければ、そのままの位置に置く。そうでなければ、左側の値より大きくなるまで移動させる。
• すべての要素が正しい順序になるまで繰り返す。

これで配列がソートされました。挿入ソートは一度に一つの要素を処理していきます。次に、このソートアルゴリズムをJavaで実装する方法を見ていきましょう。

Javaで挿入ソートを実装する方法

挿入ソートでは、比較対象の2つの値のうち大きい方の値が、ソート処理が実行されるたびに一つ右の位置へ挿入されていきます。

理論的な話はここまでにして、実際にJavaでどのように実装するのかを見てみましょう。ここでは、学生の成績リストを挿入ソートで並べ替えるクラスを作成します。

Arraysライブラリの準備

まず、JavaプログラムにArraysライブラリをインポートします。このライブラリは、ソート後のリストをコンソールに出力する際に使用します。

import java.util.Arrays;

ソート用メソッドの宣言

続いて、リストを走査してデータを昇順に並べ替えるメソッドを宣言します。

class SortGrades {
public static void insertionSort(int [] numbersToSort) {
	int itemCount = numbersToSort.length;

	for (int value = 1; value < itemCount; value++) {
		int key = numbersToSort[value];
		int last = value - 1;

		while (last >= 0 && key < numbersToSort[last]) {
			numbersToSort[last + 1] = numbersToSort[last];
			--last;
		}

		numbersToSort[last + 1] = key;
	}
}
}

まず、入力配列の要素数を取得します。これにより、リスト内のすべての要素を走査するループを作成できます。forループを初期化し、リストがソートされるまで繰り返し処理を行います。

forループの中では、「key」と「last」という2つの変数を宣言しています。

変数「key」は、現在ソート中の要素を追跡します。「last」は、その要素の左側にある比較対象の要素を追跡します。

プログラムは、「key」の値を左側の各要素と比較し、より小さい要素が見つかるまで処理を続けます。この処理はwhileループ内で行われます。

main関数の定義

このコードをこのまま実行しても、何も起こりません。まだmain関数を定義していないからです。そこで、int型の配列（数値の配列）を定義するmain関数を作成しましょう。このmain関数は、先ほど宣言したinsertionSort()メソッドを使って数値をソートします。insertionSortメソッドの宣言の後に、以下のコードを追加してください。

public static void main(String args[]) {
	int[] numbers = { 8, 6, 3, 9 };
	SortGrades sortNumbers = new SortGrades();
	sortNumbers.insertionSort(numbers);

	String arrayToString = Arrays.toString(numbers);
	System.out.println("Sorted list: " + arrayToString);
}

mainメソッドでは、ソートしたい数値のリストを宣言しています。そして、SortGradesクラスのインスタンスsortNumbersを作成し、このメソッドを使って数値リストを昇順にソートします。このメソッドはnumbers配列の中身を直接書き換えるため、別途結果を格納する配列を用意する必要はありません。

その後、Arrays.toString()メソッドを使ってnumbers配列を文字列に変換し、ソート済みのリストをコンソールに出力しています。

計算量（オーダー）の確認

挿入ソートの平均計算量はO(n²)です。これは、要素がまったくソートされていない状態の場合に発生します。

一方、配列がすでにソートされている場合は最良のケースとなり、計算量はO(n)になります。これは、挿入ソートの内部ループがまったく実行されないためです。

最悪のケースでは、挿入ソートの計算量はO(n²)になります。これは、配列が昇順（または降順）に並んでいて、それを逆順にソートしたい場合などに発生します。この場合、すべての要素が他のすべての要素と比較されることになります。

まとめ

挿入ソートは、データを効率的に並べ替える手法の一つです。挿入ソートはリストの2番目の要素から比較を始め、その値が左側の値より大きければリストはそのまま変わりません。そうでなければ、左側の値が自分より小さくなるまで要素を移動させます。

これで、あなたもJavaで独自の挿入ソートアルゴリズムを書く準備が整いました！さらにJavaの学習を深めたい方は、ぜひ関連ガイドも参考にしてみてください。