Java で配列をソートする方法

並べ替えは、プログラミングにおいて最も一般的で必要な操作の 1 つです。これは、特定の順序での要素のセットの順序を表します。この記事では、Java で配列をソートするための標準的な方法について説明します。

並べ替えについて簡単に説明すると、

つまり、並べ替えとは一連のデータを並べ替えることです。私たちの場合は配列です。配列やその他のデータ構造を並べ替える目的は、コレクション内のデータの検索、操作、解析を容易にすることです。プログラマはソートを頻繁に必要とするため、どのプログラミング言語にも配列、リスト、その他の順序付けされたデータ構造をソートするためのメソッドが組み込まれています。このようなメソッドを使用するには、それらを呼び出します。操作は可能な限り簡略化されています。通常、組み込みメソッドは最大限に最適化されます。ほとんどの場合、仕事やプロジェクトに使用することは良い考えです。ただし、ほとんどすべてのプログラマーは、勉強中にソート アルゴリズムを自分で実装する必要があります。したがって、これらの完璧な演習では、プログラミングの本質を理解することができます。さらに、仕事上、標準以外の並べ替え方法が必要になる場合もあります。多くの並べ替えアルゴリズムがあります。データセットの種類やサイズに応じて、長所と短所があります。標準の並べ替えアルゴリズムには、バブル ソート、選択ソート、挿入ソート、マージ ソート、クイックソートなどがあります。

Java で配列をソートするための組み込みメソッド: Arrays.sort

最も単純なものから始めましょう。Java で配列をソートするメソッドをすでに誰かが書いてくれています。このメソッドはArraysクラス、具体的にはjava.util.Arraysにあります。このクラスには、並べ替えや検索など、配列を操作するためのさまざまなメソッドが含まれています。Arrays.sortメソッドは、文字列、整数、その​​他の要素が含まれているかどうかに関係なく、Java で配列を並べ替える便利な方法を提供します。Java のArrays.sortメソッドにはいくつかのバリエーションがあります。Arraysクラスで一般的に使用される並べ替えメソッドをいくつか示します。

• Arrays.sort(Array) : プリミティブ型またはオブジェクトの配列を昇順に並べ替えるのに使用します。要素の自然な順序が使用されます。
• Arrays.sort(Array, fromIndex, toIndex) : このオーバーロードされた並べ替えメソッドを使用すると、fromIndex パラメーターと toIndex パラメーターで指定された配列の一部のみを並べ替えることができます。
• Arrays.sort(Array, comparator) : これは、カスタム コンパレータを使用してオブジェクトの配列を並べ替えるためのものです。コンパレータは要素の順序を定義します。
• Arrays.ParallelSort(Array) : このメソッド バージョンは、パフォーマンスを向上させるために複数のスレッドを利用して、配列を並列に並べ替えます。これは、大きな配列をソートする場合に役立ちます。
• Arrays.ParallelSort(Array, fromIndex, toIndex) : このオーバーロードされたバージョンのParallelSort メソッドを使用すると、 Array 内の特定の範囲の要素を並べ替えることができます。

これらを使用すると、自然な順序に基づいて、またはカスタム コンパレータを使用して、要素をすばやく配置できます。このメソッドを 2 つの例で見てみましょう。1 つは文字列を使用した例です。

例 1: 文字列の並べ替え

「ヴァイオリン」、「ヴィオラ」、「チェロ」、「コントラバス」という一連の弦楽器があるとします。Array.sortメソッドを使用して、それらをアルファベット順に並べることができます。

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

出力は次のとおりです。 このプログラムでは、まずjava.util.Arraysクラスをインポートして、 Array.sortメソッドにアクセスします。次に、楽器名を含むinstrumentsという文字列配列を作成します。その後、Arrays.sort(instruments)を呼び出します。したがって、このメソッドは配列を取得し、要素を自然な順序 (アルファベット順) に基づいて昇順に並べ替えます。最後に、ソートされた配列をループし、各楽器を出力します。

例 2: 整数の並べ替え

整数の配列を昇順に並べ替える別の例を考えてみましょう。

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

出力： ここでは、ソートされていないいくつかの要素を含む、numbers という整数配列を作成します。次に、 Arrays.sort(numbers)を呼び出して、配列を昇順に並べ替えます。Array.sortメソッドは元の配列をその場で変更することに注意してください。したがって、元のArrayを保持するには、並べ替える前にコピーを作成します。

例 3: 降順

降順ソートについてはどうですか? Arrays.sortを使用すると簡単です。カスタム コンパレータを使用するだけです。以下に例を示します。

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

出力は次のとおりです。 ここには、number という名前の整数の配列があります。Arrays.sortメソッドの 2 番目の引数としてComparator.reverseOrder()を渡すことで、要素を降順に並べ替えるカスタム コンパレーターを指定します。Comparator.reverseOrder ()メソッドは、要素の自然な順序を逆にするコンパレータを返します。Comparator.reverseOrder()メソッドにはオブジェクトが必要であるため、ここではプリミティブ int 型の代わりに Integer ラッパー クラスを使用していることに注意してください。プリミティブな int 値の配列がある場合は、このアプローチを使用する前に、それらをIntegerオブジェクトに変換する必要もあります。カスタム コンパレータを使用すると、 Java の Arrays.sortメソッドを使用して配列を降順で簡単に並べ替えることができます。

Java で独自に作成した古典的なソート アルゴリズム

コンピュータ サイエンスを独学で勉強している場合、または大学で勉強している場合は、配列の並べ替えの割り当てをすでに見たことがあります。さまざまな並べ替えアルゴリズムがあり、この記事ではそのうちのいくつかを実装します。一般に、アルゴリズムの実装が簡単であればあるほど、効率は低くなります。プログラマーはアルゴリズムの効率を測定します。アルゴリズムの効率は、アルゴリズムの動作時間とリソースに費やされるメモリによって測定されます。それは私たちの記事の主題ではありませんが、Java の Arrays.sort が効果的なアルゴリズムであることについては言及します。

バブルソート

学生の間で最も人気のあるアルゴリズムであるバブルソートから始めましょう。それは簡単です。アルゴリズムは 2 つの要素を比較し、順序が間違っている場合はそれらを交換し、これを配列の最後まで繰り返します。ソーダの泡が上部に弾けるように、小さな要素がArrayの最後まで「浮いている」ことがわかります。

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

ここで、メソッドは入力として整数の配列を受け取ります。外側のループは 0 から n-1 まで進みます。ここで、n は配列のサイズです。内側のループは隣接する要素を比較します。順序が間違っている場合、メソッドは順序を入れ替えます。この手順は、配列全体がソートされるまで繰り返されます。プログラムの出力は次のとおりです。

選択範囲の並べ替え

選択アルゴリズムは、ソートされていない部分から最小の要素を繰り返し見つけて先頭に配置することによって配列をソートします。Javaで書いてみましょう:

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

プログラムの出力は次のとおりです。 順を追って説明しましょう。外側のループは、配列の先頭から最後から 2 番目の要素 (n-1 まで) まで反復します。このループは、 Arrayの未ソート部分の開始点として各要素を 1 つずつ選択します。外側のループ内で、minIndex を現在のインデックスiに初期化し、それがArrayの未ソート部分の最小項目のインデックスであると想定します。内側のループはi+1から始まり、 Arrayの最後の要素まで進みます。各要素を現在の最小要素 ( arr[minIndex] ) と比較することにより、配列の未ソート部分内の最小項目のインデックスを検索します。現在の最小要素よりも小さい要素が見つかった場合は、minIndex を新しい最小要素のインデックスに更新します。内側のループが完了すると、 Arrayの未ソート部分の最小要素のインデックスが見つかります。次に、一時変数 temp を使用して、最小要素を未ソート部分の最初の要素と交換します。外側のループはすべての要素がソートされるまで継続し、 Arrayのソートされた部分を徐々に拡張します。最後に、並べ替えられた配列が、 selectionSortメソッドの呼び出しの前後に main メソッドで出力されます。

マージソート

マージ ソートは、配列をより小さいサブ配列に再帰的に分割し、それらをソートしてから、それらをマージしてソートされた配列を取得する分割統治アルゴリズムです。マージ ソートは安定しており、特に安定性と保証された最悪の場合の時間の複雑さが必要な場合に広く使用されています。

public class MergeSort {

      //Merge Sort array
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ここでの出力は次のとおりです。 それがどのように機能するかをより正確に説明しましょう。このアルゴリズムは、基本ケースに達するまで (配列の要素が 1 つまたはゼロの場合)、配列を再帰的に 2 つの部分に分割します。次に、merge メソッドを使用して、ソートされた半分を再度マージします。マージ メソッドは、元の配列と左右のサブ配列 (左と右) の 3 つの配列を入力として受け取ります。左右の部分配列の要素を比較し、それらをソートされた順序で 元の配列にマージします。

挿入ソート

挿入ソートは、ソートされていない部分の要素をソートされた部分の正しい位置に繰り返し挿入することによって機能します。小規模なデータ セットまたはほとんど並べ替えられたデータに対しては良好なパフォーマンスを発揮します。

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

プログラムの出力は通常と同じです。 ここで、insertionSortメソッドは挿入ソート アルゴリズムを実装します。配列を反復処理し、各要素をキーと見なします。キーとその前の要素を比較し、キーの方が大きい場合は 1 つ前に移動し、要素を効果的にシフトして正しい位置にキーのためのスペースを確保します。 外側のループは、配列の 2 番目の要素 ( i = 1 ) から最後の要素まで反復します。内部ループは現在の要素 ( arr[i] ) から開始され、キーの正しい位置が見つかるか Array の先頭に到達するまで逆方向 ( j = i - 1 ) に進みます。内側のループ内で、要素 ( arr[j] ) がキーより大きい場合、要素は 1 つ前にシフトされ ( arr[j + 1] = arr[j] )、キー用のスペースが確保されます。このプロセスは、キーの正しい位置が見つかるまで続きます。内側のループが完了すると、キーは正しい位置に配置されます ( arr[j + 1] = key )。main メソッドでは、 insertSortメソッドを使用した並べ替えの前後にサンプル配列が作成され、出力されます。

クイックソート

クイック ソートは、ピボット要素を選択し、ピボットを中心に配列を分割する分割統治アルゴリズムです。一般に、小規模および中規模のデータ セットの場合、定数係数が低いため、クイック ソートはマージ ソートより高速です。

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

出力は次のとおりです。 ここでは、クイックソートを実装するための 3 つの方法を紹介します。QuickSortメソッドは、並べ替える配列、部分配列の下位インデックス、および部分配列の上位インデックスの 3 つのパラメーターを受け取ります。最初に、部分配列に複数の要素があるかどうかをチェックします。存在する場合、パーティション メソッドを使用してピボットを選択し、ピボットの前で部分配列を再帰的に並べ替え、ピボットの後で部分配列を再帰的に並べ替えます。パーティション メソッドは、ピボットを部分配列 ( arr[high] ) の最後の要素として選択します。パーティション インデックス (i) を下位インデックス - 1 に設定します。次に、下位インデックスから上位インデックス - 1 まで反復し、各要素がピボット以下であるかどうかを確認します。そうである場合、要素をパーティション インデックス (i) の要素と交換し、パーティション インデックスをインクリメントします。最後に、ピボット要素をパーティション インデックス + 1 の要素と交換し、パーティション インデックスを返します。パーティション メソッドは、ピボットを部分配列 ( arr[high] ) の最後の要素として選択します。パーティション インデックス (i) を下位インデックス - 1 に設定します。次に、下位インデックスから上位インデックス - 1 まで反復し、各項目がピボット以下であるかどうかを確認します。そうである場合、要素をパーティション インデックス (i) の要素と交換し、パーティション インデックスをインクリメントします。最後に、ピボット要素をパーティション インデックス + 1 の要素と交換し、パーティション インデックスを返します。swap メソッドは、 Array内の 2 つの要素を交換するために使用されるユーティリティ メソッドです。mainメソッドでは、 quickSortメソッドを使用した並べ替えの前後にサンプル配列が作成され、出力されます。

結論

この記事では、Java 言語で配列を並べ替える方法を学びました。組み込みのArrays.sortメソッドを使用することも、バブル ソートやマージ ソートなどの一般的な並べ替えメソッドの独自の実装を作成することもできます。また、独自の並べ替え方法に侵入してみることもできます。それはあなたのタスクによって異なります。並べ替えの問題を迅速に解決する必要がある場合は、あらかじめ作成されたメソッドを使用してください。プログラミングを学び、さらに上達したい場合は、いくつかの並べ替えメソッドを自分で作成することをお勧めします。