Javaでの挿入ソート：ハウツーガイド

Java挿入ソートは、リスト内の各項目を評価します。アイテムが前のものよりも少ない場合、ソートはアイテムを交換します。それ以外の場合、アイテムは同じ場所にとどまり、次の2つのアイテムがリストで比較されます。

コンピュータはアイテムのリストをソートするのが得意です。ループを使用すると、リスト内のすべてのアイテムを検索し、特定の方法で表示されるまで順序を変更できます。

プログラミングでは、リストをソートするためのいくつかの標準的な方法があります。これらをソートアルゴリズムと呼びます。ソートアルゴリズムは、リスト内のすべてのアイテムを読み取り、特定の一連の命令を使用してそれらをソートします。遭遇する最も一般的なソートアルゴリズムの1つは、挿入ソートです。

このガイドでは、Java挿入ソートアルゴリズムを実装する方法について説明します。この種の背後にあるロジックがどのように機能するかを学ぶことができるように、途中で例を見ていきます。

始めましょう！

Java挿入ソートとは何ですか？

Java挿入ソートは、カードゲームで手札をソートするのと同じように機能します。挿入ソートは、リスト内の各アイテムをチェックし、それらを左側のアイテムと交換します。アイテムが交換されるかどうかは、アイテムが前のアイテムよりも大きいか小さいかによって異なります。

ちょっとの間、あなたがカードゲームをプレイしていると想像してみてください–ホイスト、ラミー、何でも。カードを並べ替えるときはどうしますか？

左側から始めて、2枚目のカードがソートされているかどうかを確認します。そのカードが最後のカードよりも大きい場合は、同じ位置にとどまる必要があります。そうでなければ、リスト内の位置を上に移動する必要があります。

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

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

手札にあるすべてのカードを調べ、すべてのカードが正しい順序で表示されるまでこの操作を実行します。

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

挿入ソートは、ソートする必要のある要素が左側に数個しかない場合に最もよく使用されます。

マージソートなど、データの大きなリストをソートするために使用できるより効率的なアルゴリズムがあります。これが、挿入ソートを常にデフォルトで使用する必要がない理由です。そうは言っても、リスト内の要素を並べ替える際の挿入ソートは、バブルソートや選択ソートよりも効率的です。

挿入ソートは単純なソートアルゴリズムであり、初心者が学ぶのに適しています。

挿入ソートのウォークスルー

カードのデッキを視覚化することは、世界で最も直感的ではありません。プログラミングの例を見ていきましょう。次のリストを検討してください：

8

6

3

9

このリストでは、最初の要素がソートされていると想定しています。

次のステップは、リストの2番目の項目を最初の項目と比較することです。最初のアイテムが2番目のアイテムよりも大きい場合、そのアイテムは最初のアイテムの前に配置されます。

この場合、6は8よりも大きくなります。これは、6がリスト内で1つ後ろに移動し、8が1つ前に移動することを意味します。

6

8

3

9

次に、3番目の要素をその左側の要素と比較する必要があります。3は8より大きいですか？いいえ、8は位置を右に移動します：

6

3

8

9

3は6より大きいですか？いいえ、番号6を移動します：

3

6

8

9

次に、リストの4番目のアイテム（最後のアイテム）がリストの他のすべてのアイテムよりも大きいかどうかを比較する必要があります。この場合、9は、その前にあるすべてのアイテム（8、6、および3）よりも大きくなります。

リストの並べ替えに使用したアルゴリズムは次のとおりです。

• 最初の要素が並べ替えられます。
• 2番目のアイテムをその左側のアイテムと比較します。
• このアイテムが左側の値より大きい場合、アイテムは同じ場所にとどまります。それ以外の場合は、値を左に移動します。
• すべてのアイテムが順番に表示されるまで繰り返します。

これで、ソートされた配列ができました。挿入ソートは、一度に1つのアイテムをソートします。この並べ替えアルゴリズムをJavaで実装する方法について説明しましょう。

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

比較されている2つの値の最大値は、並べ替え関数が実行されるたびに1つ右の位置に挿入されます。

これについては理論的にはよく話されていますが、Javaでどのように実装しますか？それは良い質問です。生徒の成績のリストに対して挿入ソートを実行するクラスを作成しましょう。

アレイライブラリを準備する

まず、ArraysライブラリをJavaプログラムにインポートします。並べ替えたら、このライブラリを使用してリストをコンソールに出力します：

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つの変数を宣言しました。

「キー」Java変数は、現在ソートしているアイテムを追跡します。 「最後の」変数は、アイテムの左側でソートする必要のあるアイテムの数を追跡します。

このプログラムでは、小さい要素が見つかるまで、「key」の値を左側の各要素と比較します。これは、Javaの「while」ループで発生します。

主な機能を定義する

このコードを実行しても、何も起こりません。これは、主な機能をまだ定義していないためです。 int配列（数値の配列）を定義するmain関数を定義しましょう。このメイン関数はinsertionSort（）を使用します これらの数値をソートするために宣言した関数。挿入ソートJavaメソッドを宣言した後、このコードを貼り付けます：

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

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

mainメソッドでは、並べ替える数値のリストを宣言しました。 InsertionSort（）のインスタンスを作成しました sortNumbersというメソッド 。このメソッドを使用して、番号のリストを昇順で並べ替えます。このメソッドは、「numbers」配列内の値を変更します。値を格納するための個別の配列を宣言していません。

次に、 Arrays.toString（）を使用しました 数値配列を文字列に変換するメソッド。ソートされたリストをコンソールに出力します。

複雑さのレビュー

挿入ソートの平均的なケースの複雑さはO（n ^ 2）です。これは、要素がソートされていない場合に発生します。

配列がソートされている場合、最良の場合の複雑さが発生します。これにより、O（n）の時間計算量が得られます。これは、この場合、挿入ソートの内部ループがまったく実行されないためです。

最悪の場合、挿入ソートはO（n ^ 2）で実行されます。これは、配列が昇順または降順であり、逆に並べ替える（つまり、昇順から降順）場合に発生します。これには、すべての要素を他のすべての要素と比較することが含まれます。

結論

挿入ソートは、データをソートする効率的な方法です。挿入ソートは、リストの2番目から始まる値を比較します。この値が左側の値より大きい場合、リストは変更されません。それ以外の場合は、左側のアイテムがそれより小さくなるまで値が移動されます。

これで、Javaで独自の挿入ソートアルゴリズムを作成する準備が整いました。その他のJava学習リソースをお探しの場合は、Javaの学習方法ガイドをご覧ください。