Javaでの挿入ソート

配列のソートは、Java 初心者が知っておくべき最も一般的な操作の 1 つです。配列はデータを整理するのに常に最も便利な方法ではなく、これは主に少数の場合に当てはまりますが、配列の並べ替えの背後にある概念は、複雑なソフトウェアやデータ サイエンスに数多く応用できます。この記事では、挿入ソートとは何かについて詳しく説明します。この概念を完全に理解できるように、いくつかの例と練習問題を含めました。

挿入ソートとは何ですか?

基本的に、挿入ソートは開発者が小さな数値の文字列を整理するために使用するアルゴリズムです。すべての値を 2 つのスタック (ソートされたスタックとソートされていないスタック) に分割します。「未分類」のスタック内の数字が 1 つずつ選択され、正しい順序に並べられます。挿入ソートの入力と出力を詳しく見てみましょう。

• 入力: ソートされていない数値要素を含む配列 A: A[0,1, n, n-2...]。
• 出力: 同じ数値を含むが完全にソートされた配列。これは通常、B: B[0]B[1]...B[n-1] と呼ばれます。

挿入ソートを使用するにはいくつかの方法があります。最も一般的な方法は次のとおりです。

• 数値ソート（昇順）：[1、2、3、4、5]
• 数値ソート（降順）：[5、4、3、2、1]
• アルファベット順の並べ替え: [a、b、c、d]

注:空の配列またはシングルトンがある場合、これらはデフォルトでソートされているとみなされます。

挿入ソートの理論を理解する

挿入ソートの背後にあるコードを調べる前に、専門用語以外を使用してアルゴリズムを詳しく見てみましょう。昇順で並べ替えるコードを示すので、この投稿ではアルゴリズムをステップごとに説明するのが理にかなっています。 ステップ 1.arr[1]との間を繰り返します。arr[n]ここで、nは通常 10 未満の数値です。 ステップ 2.メソッドを使用して、選択した要素 ( として知られていますkey) をシーケンス内の前の数値と比較しますsort()。 ステップ 3.すべての要素が後続要素よりも小さい場合は、より大きな値が見つかるまで比較を繰り返します。 ステップ 4.大きい値を小さい値より 1 つ上の位置に交換して、順序付けされたシーケンスを作成します。 ステップ 5.ソートされた文字列が得られるまでプロセスを繰り返します。

プリミティブ配列のソート

このアルゴリズムは最も単純な Java 操作の 1 つであるため、まったくの初心者でも実装にそれほど問題はありません。配列を並べ替えるステップバイステップのガイドは次のとおりです。

1. ソート用の配列を宣言する

まず、後で Java を使用して表示する値の文字列を作成しましょう。挿入ソートを使用するには、配列を作成する必要があります。そのためには、使用しますint[]

int[] arrayA = {10, 14, 20, 30};

2. sort_arr を使用してアルゴリズムを実装する

sort_arr メソッドは、挿入ソートを実装する最も一般的な方法の 1 つです。実際には次のようになります。

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. ループとイテレータを作成する

挿入ソートアルゴリズムでループを使用すると、開発者は要素ごとにロジックを繰り返す必要がなくなります。ループの作成は複雑に見えますが、非常に簡単です。例を次に示します。

for(int i=0; i< sort_arr.length; ++i){

ループが機能するようになったので、すべての要素を希望の順序で並べ替えるイテレータを作成します。以降、イテレータを「j」と呼びます。

        int j = i;

4. 「while ループ」の作成

挿入ソートに関しては、新しいソートされた配列には「while」ループが不可欠です。昇順挿入ソート用に設定するには、開発者は次の 2 つの条件を満たす必要があります。

• j に割り当てられる値は 0 より大きくなければなりません
• に割り当てられる値はインデックスj-1より大きい必要がありますj

while ループ内の両方の条件が true になるとすぐに、配列のキー値はインデックスと等しくなりますj。

5. 配列のソート

while ループを設定すると、while ループ内の条件の一方または両方が失敗するまで、jと の値が交換されます。j-1同様に、for ループ条件も失敗するまで、for ループ内のすべての値に対して並べ替えが繰り返されます。実際に挿入ソートのプロセスがどのように機能するかは次のとおりです。

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

ArrayList のソート

挿入ソートの背後にある数学を理解することは重要ですが、実際のソフトウェア開発となると、プリミティブ配列内のシーケンスよりも ArrayList をソートすることになります。ArrayList を並べ替えるステップバイステップのガイドは次のとおりです。

1. Elementコレクションに属する項目の 新しいクラスを作成します。

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. コレクション内にはcompareTo()メソッドがあります。これを使用して 2 つの要素の ID を比較します。

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. アルゴリズムを適用し、オブジェクトをArrayList比較する代わりに並べ替えるループをいくつか作成します。

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. 以下に示すように、さらに要素を追加することもできますArrayList。

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. 次は並べ替えの時間です。

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. 次に、入力と出力を比較して、間違いがないことを確認しましょう。例として使用した文字列の比較を次に示します。

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

挿入ソートの練習問題

この並べ替えアルゴリズムのコツを理解したら、次は理論的および実践的なスキルをテストします。 理論クイズ #1 配列 [1, 4, 6, 8] が与えられ、それに新しい要素 n = 7 を追加します。並べ替えられた一連の数値を取得するには、何回の比較を行う必要がありますか? 配列内のインデックス n の最終値を示します。 理論クイズ #2 就職面接で、チーム リーダーから、ソート挿入が非効率な方法であることを証明するように求められます。[0, 3, 6, 8, 9] の数値列が与えられた場合、ソートに必要な実行時間を最大化するには、入力シーケンスの順序はどうあるべきですか? 練習問題 Java の挿入ソートを使用して、[0, 1, 4, 5, 2, 3, 7, 9, 8] 配列を昇順にソートします。

結論

挿入ソートを理解する上での最大の課題は、そのプロセスがどのように機能するかを理解することです。コツを掴めば、テンプレートをコードに変換するのは簡単です。関連する練習問題を時間をかけて練習し、再検討する限り、挿入ソートの速度は急速に向上します。