ادغام مرتب سازی در جاوا

Merge Sort چیست؟

مرتب سازی ادغام رایج ترین الگوریتم برای مرتب سازی داده ها با استفاده از تکنیک " تقسیم و غلبه " است. در این الگوریتم مسئله به زیرمسائل تقسیم می شود و پس از مرتب سازی با هم ادغام می شوند. بگذارید بگوییم فهرستی از اعداد مرتب نشده داریم که حاصل یک کلاس برای یک موضوع خاص است. برای مرتب کردن آنها بر اساس صعودی باید آنها را در لیستی قرار دهیم که از کم به بالا شروع می شود. در این الگوریتم مرتب سازی ادغام، لیست به لیست های کوچکتر تقسیم می شود تا آنها را به ترتیب صعودی مرتب کند و سپس نتایج را برای درک بهتر ادغام می کند. مرتب سازی ادغام در جاوا را می توان از طریق مثالی از یک آرایه توضیح داد {6،9،8،2،4،1}، آن را به عنوان نتیجه یک آزمون کلاس از 10 در نظر بگیرید. آرایه (نتایج) به طور مکرر تقسیم می شود. به تکه های کوچکتر تا زمانی که اندازه آنها 1 شود. سپس فرآیند ادغام در حالی که اعداد به طور همزمان مرتب می شوند انجام می شود. این به ما نتیجه ای می دهد که از کمترین امتیاز شروع می شود تا بالاترین امتیاز دریافت شده است. این آرایه به دو آرایه تقسیم می شود که هر کدام شامل 3 عنصر است که در مرحله 2 در زیر نشان داده شده است و تا زمانی که در مرحله 4 به وحدت برسد به تقسیم شدن ادامه می دهد . سپس الگوریتم Merge Sort شروع به مرتب کردن اعداد یک مرحله ای در یک زمان می کند ( مرحله 5 ) و سپس اعداد را در یک آرایه بزرگتر در مراحل 6 و 7 ادغام می کند .

پیاده سازی

در پیاده سازی، کدی را برای الگوریتم مرتب سازی ادغام در جاوا خواهیم نوشت. متغیرهای مورد نیاز آرایه ورودی و طول آرایه خواهند بود. این دو پارامتر بیشتر برای معرفی پارامترهای بیشتر برای ایجاد تابع مرتب سازی ادغام استفاده خواهند شد. بیایید برای درک عملکرد کلی الگوریتم مرتب سازی ادغام در جاوا، به قطعه زیر نگاهی بیندازیم.

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 Beginning و End برای تعیین Middle استفاده می شود. سپس در مرحله بعد 2 زیرآرایه جدید از ابتدا تا وسط و دیگری از وسط +1 تا انتها ایجاد می شود. این آرایه ها تا زمانی تقسیم می شوند که طول آنها 1 شود و سپس از طریق تابع Merge زیرآرایه های مرتب شده Beginning، Middle، Middle+1 و End همه دوباره ادغام می شوند تا راه حل را بدست آورند.

مثال

کد زیر در جاوا الگوریتم مرتب سازی ادغام را توضیح می دهد:

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

خروجی

نتیجه

Merge Sort در جاوا یک الگوریتم ساده برای به دست آوردن یک لیست مرتب شده از لیست مرتب نشده اعداد است. روش اصلی " تقسیم و غلبه " برای دسترسی به آرایه مرتب شده از یک آرایه مرتب نشده استفاده می شود.