Gabung Isih dalam Java

Apa itu Merge Sort?

Isih Gabung ialah algoritma yang paling biasa untuk mengisih data menggunakan teknik " bahagi dan takluk ". Dalam algoritma ini, masalah dibahagikan kepada submasalah dan kemudian selepas menyusun ia digabungkan bersama. Katakan kita mempunyai senarai nombor yang tidak diisih, hasil daripada kelas untuk subjek tertentu. Untuk menyusunnya mengikut tertib menaik, kita perlu meletakkannya dalam senarai bermula dari rendah ke tinggi. Dalam algoritma Isih Gabung ini, senarai akan dibahagikan kepada senarai yang lebih kecil untuk mengisihnya ke dalam susunan menaik dan kemudian ia akan menggabungkan hasil untuk pemahaman yang lebih baik. Merge Sort dalam Java boleh dijelaskan melalui contoh tatasusunan {6,9,8,2,4,1}, pertimbangkan ia sebagai hasil ujian kelas daripada 10. Tatasusunan (hasil) akan dibahagikan berulang kali kepada ketulan yang lebih kecil sehingga saiznya 1. Kemudian proses penggabungan berlaku sambil menyusun nombor secara serentak. Ini akan memberikan kita keputusan yang bermula dengan markah terendah hingga markah tertinggi yang diterima. Tatasusunan ini akan dibahagikan kepada dua tatasusunan yang akan mengandungi 3 elemen setiap satu seperti yang ditunjukkan di bawah dalam langkah 2 dan ia terus membahagikan sehingga perpaduan dicapai dalam langkah 4 . Kemudian algoritma Merge Sort mula mengisih nombor satu langkah pada satu masa ( langkah 5 ) dan kemudian menggabungkan nombor ke dalam tatasusunan yang lebih besar dalam langkah 6 & 7 .

Perlaksanaan

Dalam pelaksanaannya kami akan menulis kod untuk algoritma isihan gabungan dalam Java. Pembolehubah yang diperlukan ialah tatasusunan input dan panjang tatasusunan. Kedua-dua parameter ini selanjutnya akan digunakan untuk memperkenalkan parameter selanjutnya untuk mencipta fungsi isihan gabungan. Mari kita lihat coretan di bawah untuk memahami kerja umum Algoritma Isih Gabung di Jawa.

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

Mula-mula melalui keadaan if Mula dan Akhir digunakan untuk menentukan Tengah. Kemudian dalam langkah seterusnya, 2 subarray baharu dicipta bermula dari Permulaan hingga Pertengahan dan satu lagi bermula dari +1 Tengah hingga Akhir. Tatasusunan ini dibahagikan sehingga panjangnya menjadi 1 dan kemudian melalui Fungsi Gabungan, subarray yang diisih Permulaan, Tengah, Tengah+1 dan Tamat semuanya digabungkan kembali untuk memperoleh penyelesaian.

Contoh

Kod berikut dalam Java menerangkan algoritma pengisihan 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");
    }
}

Pengeluaran

Kesimpulan

Merge Sort dalam Java ialah algoritma mudah untuk memperoleh senarai diisih daripada senarai nombor yang tidak diisih. Kaedah asas ' bahagi dan takluk ' digunakan untuk mengakses tatasusunan yang diisih daripada tatasusunan yang tidak diisih.