Pagsamahin ang Pag-uuri sa Java

Ano ang Merge Sort?

Ang Merge Sort ay ang pinakakaraniwang algorythm para sa pag-uuri ng data gamit ang " divide and conquer " technique. Sa algorithm na ito, ang problema ay nahahati sa mga subproblema at pagkatapos ay pagkatapos pag-uri-uriin ang mga ito ay pinagsama-sama. Sabihin nating mayroon tayong listahan ng mga hindi pinagsunod-sunod na numero, ang resulta ng isang klase para sa isang partikular na paksa. Upang pag-uri-uriin ang mga ito sa pamamagitan ng pataas na pagkakasunud-sunod, kakailanganin nating ilagay ang mga ito sa isang listahan simula sa mababa hanggang sa mataas. Sa algorithm na ito ng Merge Sort, hahatiin ang listahan sa mas maliliit na listahan upang pagbukud-bukurin ang mga ito sa isang pataas na pagkakasunud-sunod at pagkatapos ay pagsasamahin nito ang mga resulta para sa mas mahusay na pag-unawa. Ang Merge Sort sa Java ay maaaring ipaliwanag sa pamamagitan ng isang halimbawa ng array {6,9,8,2,4,1}, isaalang-alang ito bilang resulta ng pagsubok sa klase sa 10. Ang array (ng mga resulta) ay paulit-ulit na mahahati sa mas maliliit na tipak hanggang ang kanilang sukat ay 1. Pagkatapos ay nagaganap ang proseso ng pagsasama habang pinag-uuri-uri ang mga numero nang sabay-sabay. Magbibigay ito sa amin ng resulta na magsisimula sa pinakamababang marka hanggang sa pinakamataas na markang natanggap. Ang array na ito ay hahatiin sa dalawang array na maglalaman ng 3 elemento bawat isa tulad ng ipinapakita sa ibaba sa hakbang 2 at patuloy itong naghahati hanggang sa maabot ang pagkakaisa sa hakbang 4 . Pagkatapos ay magsisimula ang algorithm ng Merge Sort na pagbukud-bukurin ang mga numero nang paisa-isa ( hakbang 5 ) at pagkatapos ay pinagsama ang mga numero sa isang mas malaking hanay sa mga hakbang 6 at 7 .

Pagpapatupad

Sa pagpapatupad, magsusulat kami ng code para sa merge sort algorithm sa Java. Ang mga variable na kinakailangan ay ang input array at ang haba ng array. Gagamitin pa ang dalawang parameter na ito para ipakilala ang mga karagdagang parameter para gawin ang merge sort function. Tingnan natin ang snippet sa ibaba upang maunawaan ang pangkalahatang paggana ng Merge Sort Algorithm sa 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

Una sa pamamagitan ng kung kundisyon Simula at Wakas ay ginagamit upang matukoy ang Gitna. Pagkatapos sa susunod na hakbang, 2 bagong subarray ang gagawin simula sa Simula hanggang Gitna at ang isa pa simula sa Gitna +1 hanggang Katapusan. Hinahati ang mga array na ito hanggang sa maging 1 ang haba ng mga ito at pagkatapos ay sa pamamagitan ng Merge Function ang mga pinagsunod-sunod na subarray na Simula, Gitna, Gitna+1 at Wakas lahat ay pinagsama-sama pabalik upang makuha ang solusyon.

Halimbawa

Ipinapaliwanag ng sumusunod na code sa Java ang merge sort algorithm:

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

Konklusyon

Ang Merge Sort sa Java ay isang simpleng algorithm upang makakuha ng isang pinagsunod-sunod na listahan mula sa isang hindi pinagsunod-sunod na listahan ng mga numero. Ang pangunahing paraan ng ' divide and conquer ' ay inilapat upang ma-access ang pinagsunod-sunod na hanay mula sa isang hindi pinagsunod-sunod na hanay.