Javaでの挿入ソート

プログラマーであれば、ソートについてすでによく聞いたことがあるはずです。並べ替えとは、基本的に要素を昇順または降順に並べることです。要素の並べ替えに使用できる並べ替えアルゴリズムは非常に多く、アルゴリズムごとに並べ替え方法や複雑さが異なります。したがって、どのアルゴリズムを使用するかは、特定のシナリオと要素の数によって異なります。挿入も一般的に使用される並べ替えアルゴリズムの 1 つで、複雑さは O(n^2) で、手の中のトランプを並べ替えるのと同じように実行されます。このトピックでは、Java の挿入ソートについて学習します。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

Java での挿入ソートはどのように機能しますか?

例を使用して挿入ソートの仕組みを理解しましょう。

以下の要素を含む arr という名前の配列があるとします。

10 5 8 20 30 2 9 7

ステップ #1 – 挿入ソートは、それ自体で並べ替えられた配列の 1 番目の要素を考慮して、配列の 2 番目の要素、つまり 5 から始まります。ここで要素 5 は 10 と比較されます。5 は 10 未満であるため、10 は 1 つ前に移動され、その前に 5 が挿入されます。

結果の配列は次のようになります:

5 10 8 20 30 2 9 7

ステップ #2 – 要素 arr[2]、つまり 8 が要素 arr[1]、つまり 10 と比較されます。8 はその前の要素 10 より小さいため、1 つシフトされます。その位置から 1 つ先に進み、5 と比較されます。8 は 5 より大きいため、その後に挿入されます。

結果の配列は次のようになります:

5 8 10 20 30 2 9 7

ステップ #3 – 要素 20 は 10 より大きいため、10 と比較され、その位置に残ります。

5 8 10 20 30 2 9 7

ステップ #4 – 要素 30 は 20 と比較され、要素 30 は 20 より大きいため、変更は行われず、配列はそのまま残ります。配列は

になります。

5 8 10 20 30 2 9 7

ステップ #5 – 要素 2 は 30 より小さいため 30 と比較され、1 つ前にシフトされてから 20、10、8、5 と 1 つずつ比較され、すべての要素が 1 つ前にシフトされ、2 が 5 の前に挿入されます。

結果の配列は次のとおりです:

2 5 8 10 20 30 9 7

ステップ #6 – 要素 9 は 30 より小さいため、30 と比較されます。 20、10と順番に比較され、要素が1つ前にシフトされ、10の前と8の後に9が挿入されます。

結果の配列は次のとおりです:

2 5 8 9 10 20 30 7

ステップ #7 – 要素 7 は 30 と比較され、要素 7 は 30 より小さいため、30、20、10、9、8 と比較され、すべての要素が 1 位置シフトされます。 1 つずつ前に進み、8 の前に 7 が挿入されます。

結果の配列は次のようになります:

2 5 7 8 9 10 20 30

このようにして、配列のすべての要素が挿入ソートを使用してソートされ、前の要素との比較が開始されます。

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

Java の挿入ソートは、すべての小さなデータ セットに適したシンプルなソート アルゴリズムです。

コード:

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

出力:

12 15 18 21 23 52 61

説明:

• 上記の挿入ソートのプログラムでは、insertionSort() 関数を使用して元の配列要素をソートしています。最初の要素はそれ自体でソートされているとみなされるため、ソートは 2 番目の要素から開始されます。したがって、「j」のループは配列のインデックス 1 から始まります。 「i」は、値を比較するために「j」の直前のインデックスを追跡する変数です。
key' は、ソートされた位置に配置される現在の要素の値を保持する変数です。現在値が左端の値より小さい場合はwhile()ループを実行して要素の移動処理を行い、最後に現在の要素を右位置に挿入することができます。 printArray() 関数は、ソートされた配列を最終的に出力するために使用されます。

1.ベストケース

挿入ソートでは、配列のすべての要素がすでにソートされている場合が最適です。したがって、要素を左端の要素と比較すると、常に要素の方が大きいため、要素の移動や挿入は処理されません。この場合、最良の場合の複雑さは線形、つまり O(n) になります。

2.最悪の場合

上記の挿入ソートのコードでは、最悪のケースは、配列が逆順になっている場合です。そのため、要素が左端の要素と比較されるたびに、要素は常に小さくなり、その後に必要なすべての先行要素と比較されます。配置してずらして挿入するだけです。この場合、挿入ソートの複雑さは O(n^2) です。

3.平均的なケース

平均的な場合でも、挿入ソートの複雑さは O(n^2) で、一部の要素はシフトする必要がありませんが、一部の要素は位置からシフトされ、正しい位置への挿入が実行されます。

4.最適な用途

挿入ソートは、配列のサイズがそれほど大きくない場合、または少数の要素のみをソートする必要があり、ほぼすべての要素がソートされており、一部の変更のみを行う必要がある場合に使用するのが最適です。挿入ソートは、小さいサイズの配列に対して最も高速なアルゴリズムの 1 つであり、クイック ソートよりもさらに高速です。実際、クイックソートは配列の小さな部分をソートするときに挿入ソートを使用します。

結論

上記の説明は、Java での挿入ソートの動作と実装を明確に示しています。他のプログラミング言語でも、挿入ソートを実行するロジックは同じであり、構文が変わるだけです。すべての並べ替えアルゴリズムがすべてのシナリオに適合するわけではないため、並べ替えアルゴリズムを実装する前に、並べ替えを実行する必要があるシナリオの分析を行うことが非常に重要です。

以上がJavaでの挿入ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。