Javaでのマージソート

マージソートとは何ですか?

マージ ソートは、「分割統治」手法を使用してデータをソートするための最も一般的なアルゴリズムです。このアルゴリズムでは、問題がサブ問題に分割され、並べ替えられた後、それらが一緒にマージされます。特定の科目の授業の結果である未ソートの数値のリストがあるとします。それらを昇順で並べ替えるには、それらを低いものから高いものまでリストに配置する必要があります。このマージ ソート アルゴリズムでは、リストを小さなリストに分割して昇順に並べ替え、結果をよりよく理解できるようにマージします。Java のマージ ソートは、配列 {6,9,8,2,4,1} の例で説明できます。これは 10 点満点のクラス テストの結果と考えてください。(結果の) 配列は繰り返し分割されます。サイズが 1 になるまで、より小さなチャンクに分割します。その後、数値を同時にソートしながら、マージのプロセスが実行されます。これにより、最低点から最高点までの結果が得られます。 この配列は、以下のステップ 2に示すように、それぞれ 3 つの要素を含む 2 つの配列に分割され、ステップ 4で単一に達するまで分割され続けます。次に、マージ ソート アルゴリズムが一度に 1 ステップずつ数値の並べ替えを開始し (ステップ 5 )、ステップ 6 と 7で数値をより大きな配列にマージします。

実装

実装では、Java でマージ ソート アルゴリズムのコードを作成します。必要な変数は、入力配列と配列の長さです。これら 2 つのパラメータはさらに、マージ ソート関数を作成するためのパラメータを導入するために使用されます。Java のマージ ソート アルゴリズムの一般的な動作を理解するために、以下のスニペットを見てみましょう。

Merge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
 * Array = values of the array
 * Beginning = the starting element of the array
 * End = the ending element of the array*/

if (Beginning < End) // condition check Beginning must be less than End

set Middle = (Beginning + End) / 2 // Assigning Middle to the array

Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */

Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */

Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays

end of if

End Merge_Sort_Algo

最初から if 条件までの開始と終了を使用して中間を決定します。次に、次のステップで、先頭から中間までの 2 つの新しいサブ配列と、中間 +1 から末尾までの 2 つの新しいサブ配列が作成されます。これらの配列は、長さが 1 になるまで分割され、その後、マージ関数を通じて、ソートされた部分配列の begin、middle、middle+1、および end がすべてマージされて解が取得されます。

例

Java の次のコードは、マージ ソート アルゴリズムを説明しています。

import java.util.Arrays;

class HelloWorld {

    public static void merge(

  int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
   // defining parameters

    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {  // conditions for merging

        if (new_array_1[i] <= new_array_2[j]) {
            array[k++] = new_array_1[i++];
        }
        else {
            array[k++] = new_array_2[j++];
        }
    }

    while (i < left) {
        array[k++] = new_array_1[i++];
    }

    while (j < right) {
        array[k++] = new_array_2[j++];
    }
}

    public static void mergeSort(int[] array, int length) { /** required parameters */
	if (length < 2) {  //condition for the length of array
    	return;
	}

	int middle = length / 2;  // defining new parameter middle

	int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
	int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */


	for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
    	new_array_1 [ i ] = array [ i ];
	}

	for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
    	new_array_2 [ i - middle] = array [ i ];
	}

	mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
	mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */


	merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}


    public static void main(String[] args) {

        int [ ] testScores = {6,9,8,2,4,1};
        int size = testScores.length;

        System.out.println("Original Array " + Arrays.toString(testScores) + "\n");

        mergeSort(testScores, size);

        System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
    }
}

出力

結論

Java のマージ ソートは、ソートされていない数値のリストからソートされたリストを取得する単純なアルゴリズムです。「分割統治」の基本的な方法は、ソートされていない配列からソートされた配列にアクセスするために適用されます。