Gabung Urut ing Jawa

Apa Merge Sort?

Merge Sort minangka algoritma sing paling umum kanggo ngurutake data nggunakake teknik " dibagi lan nelukake ". Ing algoritma iki, masalah dipérang dadi subproblems lan banjur sawise ngurutake padha digabungake. Ayo kita ngomong kita duwe dhaptar nomer unsorted, asil saka kelas kanggo subyek tartamtu. Kanggo ngurutake kanthi urutan munggah, kita kudu nyelehake ing dhaptar wiwit saka ngisor nganti dhuwur. Ing algoritma Merge Sort iki, dhaptar bakal dipérang dadi dhaptar sing luwih cilik kanggo ngurutake menyang urutan munggah lan banjur bakal nggabungake asil kanggo pangerten sing luwih apik. Gabung Urut ing Jawa bisa diterangake liwat conto array {6,9,8,2,4,1}, nimbang minangka asil saka test kelas saka 10. Larik (asil) bakal bola-bali dibagi. dadi potongan-potongan sing luwih cilik nganti ukurane 1. Banjur proses penggabungan ditindakake nalika ngurutake nomer kasebut bebarengan. Iki bakal menehi kita asil sing diwiwiti kanthi tandha paling murah nganti tandha paling dhuwur sing ditampa. Larik iki bakal dipérang dadi rong larik sing bakal ngemot 3 unsur saben kaya sing kapacak ing ngisor iki ing langkah 2 lan terus dipérang nganti manunggal ing langkah 4 . Banjur algoritma Gabung Urut wiwit ngurutake nomer siji-sijine ( langkah 5 ) lan banjur nggabungake nomer kasebut dadi array sing luwih gedhe ing langkah 6 & 7 .

Implementasine

Ing implementasine kita bakal nulis kode kanggo algoritma ngurutake gabungan ing Jawa. Variabel sing dibutuhake yaiku array input lan dawa array. Parameter loro iki bakal digunakake kanggo ngenalake paramèter liyane kanggo nggawe fungsi ngurutake gabungan. Coba deleng cuplikan ing ngisor iki kanggo mangerteni cara kerja umum Algoritma Urut Gabung ing 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

Pisanan liwat kondisi yen Wiwitan lan Akhir digunakake kanggo nemtokake Tengah. Banjur ing langkah sabanjure, 2 subbarrays anyar digawe wiwit saka Awal nganti Tengah lan liyane wiwit saka Tengah +1 nganti Akhir. Array iki dipérang nganti dawane dadi 1 lan banjur liwat Fungsi Gabung, subbarrays sing diurutake Awal, Tengah, Tengah + 1 lan Akhir kabeh digabung maneh kanggo entuk solusi.

Tuladha

Kode ing ngisor iki ing Jawa nerangake algoritma ngurutake 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");
    }
}

Output

Kesimpulan

Gabung Urut ing Jawa minangka algoritma prasaja kanggo entuk dhaptar sing diurutake saka dhaptar nomer sing ora diurut. Cara dhasar ' dibagi lan digdaya ' ditrapake kanggo ngakses larik sing diurutake saka larik sing ora diurutake.