Gabungkan Sortir di Java

Apa itu Pengurutan Gabung?

Merge Sort adalah algoritma paling umum untuk mengurutkan data menggunakan teknik “ dibagi dan ditaklukkan ”. Dalam algoritma ini, masalah dibagi menjadi submasalah dan kemudian setelah diurutkan, masalah tersebut digabungkan menjadi satu. Katakanlah kita memiliki daftar angka-angka yang tidak diurutkan, hasil suatu kelas untuk mata pelajaran tertentu. Untuk mengurutkannya berdasarkan urutan menaik, kita perlu menempatkannya dalam daftar mulai dari rendah ke tinggi. Dalam algoritma Merge Sort ini, daftar akan dibagi menjadi daftar-daftar yang lebih kecil untuk mengurutkannya ke dalam urutan menaik dan kemudian akan menggabungkan hasilnya untuk pemahaman yang lebih baik. Merge Sort di Java dapat dijelaskan melalui contoh array {6,9,8,2,4,1}, anggap saja sebagai hasil tes kelas dari 10. Array (hasil) akan dibagi berulang kali menjadi bongkahan-bongkahan yang lebih kecil hingga ukurannya menjadi 1. Kemudian dilakukan proses penggabungan sekaligus pengurutan angka-angka tersebut secara bersamaan. Ini akan memberi kita hasil yang dimulai dari nilai terendah hingga nilai tertinggi yang diterima. Array ini akan dibagi menjadi dua array yang masing-masing berisi 3 elemen seperti yang ditunjukkan di bawah ini pada langkah 2 dan terus terbagi hingga tercapai kesatuan pada langkah 4 . Kemudian algoritma Merge Sort mulai mengurutkan angka-angka tersebut selangkah demi selangkah ( langkah 5 ) dan kemudian menggabungkan angka-angka tersebut ke dalam array yang lebih besar pada langkah 6 & 7 .

Penerapan

Dalam implementasinya kita akan menulis kode untuk algoritma merge sort di Java. Variabel yang diperlukan adalah array input dan panjang array. Kedua parameter ini selanjutnya akan digunakan untuk memperkenalkan parameter lebih lanjut untuk membuat fungsi pengurutan gabungan. Mari kita lihat cuplikan di bawah ini untuk memahami cara kerja umum Algoritma Merge Sort di 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

Pertama melalui kondisi if Beginning dan End yang digunakan untuk menentukan Middle. Kemudian pada langkah selanjutnya dibuat 2 subarray baru yang dimulai dari Awal hingga Tengah dan satu lagi dimulai dari +1 Tengah hingga Akhir. Array ini dibagi hingga panjangnya menjadi 1 dan kemudian melalui Fungsi Gabung, subarray yang diurutkan Awal, Tengah, Tengah+1, dan Akhir semuanya digabungkan kembali untuk mendapatkan solusi.

Contoh

Kode berikut di Java menjelaskan algoritma pengurutan gabungan:

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");
    }
}

Keluaran

Kesimpulan

Merge Sort di Java adalah algoritma sederhana untuk memperoleh daftar yang diurutkan dari daftar angka yang tidak diurutkan. Metode dasar ' bagi dan taklukkan ' diterapkan untuk mengakses array yang diurutkan dari array yang tidak diurutkan.