مرتب سازی ادغامی (Merge Sort) در جاوا

سلام دوستان دراین سری از آموزش برنامه نویسی جاوا به آموزش مرتب سازی ادغامی (Merge Sort) در جاوا می پردازیم از شاید بپرسید مرتب سازی ادغامی (Merge Sort) چیست ؟ در ادامه این سوال را نیز پاسخ خواهیم داد و الگوریتم مربوط به مرتب سازی ادغامی (Merge Sort) را نیز بررسی می کنیم با ما همراه باشید.

الگوریتم مرتب سازی ادغامی (Merge Sort)

اگر طول لیست ۰ یا ۱ باشد آن پیش از این مرتب شده‌است در غیر این صورت
لیست نامرتب را به دو زیرلیست که اندازهٔ آن‌ها در حدود نصف سایز لیست اولیه‌است تقسیم می‌کند.
هر زیرلیست را به‌طور بازگشتی با صدا کردن merge sort مرتب می‌کند.
دو تا دوتا زیر لیست‌ها را از آخر ادغام می‌کند تا به یک لیست برسد.

مرتب‌سازی ادغام دو تا ایدهٔ اصلی را با هم ترکیب می‌کند تا زمان اجرایش تقویت شود.

یک لیست کوچک از گام‌های کم‌تری برای مرتب‌کردن نسبت به یک لیست بزرگ استفاده می‌کند.
یرای مرتب کردن دو لیست مرتب‌شده نسبت به دو لیست نامرتب گام‌های کمتری نیاز می‌باشد به عنوان مثال اگر این لیست‌ها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبار پیمایش کنید.

نحوه کار کرد این الگوریتم را در شکل زیر می توانید مشاهده کنید.

در ادامه مثالی از Merge Sort را برای شما قرار می دهیم.
برای اینکار سه متد نوشته شده است که در ادامه مشاهده می کنید.

 public void sort(int inputArr[]) {
        this.array = inputArr;
        this.length = inputArr.length;
        this.tempMergArr = new int[length];
        doMergeSort(0, length - 1);
    }
    private void doMergeSort(int lowerIndex, int higherIndex) {
        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            doMergeSort(lowerIndex, middle);
            doMergeSort(middle + 1, higherIndex);
            mergeParts(lowerIndex, middle, higherIndex);
        }
    }
    private void mergeParts(int lowerIndex, int middle, int higherIndex) {
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }
    }

public void sort(int inputArr[]) {

this.array = inputArr;

this.length = inputArr.length;

this.tempMergArr = new int[length];

doMergeSort(0, length - 1);

}

private void doMergeSort(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {

int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

doMergeSort(lowerIndex, middle);

doMergeSort(middle + 1, higherIndex);

mergeParts(lowerIndex, middle, higherIndex);

}

private void mergeParts(int lowerIndex, int middle, int higherIndex) {

for (int i = lowerIndex; i <= higherIndex; i++) {

tempMergArr[i] = array[i];

}

int i = lowerIndex;

int j = middle + 1;

int k = lowerIndex;

while (i <= middle && j <= higherIndex) {

if (tempMergArr[i] <= tempMergArr[j]) {

array[k] = tempMergArr[i];

i++;

} else {

array[k] = tempMergArr[j];

j++;

}

k++;

}

while (i <= middle) {

array[k] = tempMergArr[i];

k++;

i++;

}

در بالا اگر از پایین در نظر بگیریم ابتدا باید خانه کمترین وسطی و بیشترین را پیدا می کنیم این کار توسط متد mergeParts انجام می شود بعد از اینکار doMergeSort انجام می شود که در داخل آن mergeParts صدا زده شده است و در نهایت یک متد نهایی وجود دارد که نام آن sort است کافی است یک آرایه به این متد ارسال شود سپس براساس مرتب سازی ادغامی (Merge Sort) مرتب می شود.
در نهایت برای اینکه عمل Sort را انجام دهیم از متد زیر استفاده می کنیم.

int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
        MyMergeSort mms = new MyMergeSort();
        mms.sort(inputArr);
        for(int i:inputArr){
            System.out.print(i);
            System.out.print(" ");
        }

int[] inputArr = {45,23,11,89,77,98,4,28,65,43};

MyMergeSort mms = new MyMergeSort();

mms.sort(inputArr);

for(int i:inputArr){

System.out.print(i);

System.out.print(" ");

}

و در نهایت خروجی کد زیر همانند زیر می شود.

4 11 23 28 43 45 65 77 89 98

1	4 11 23 28 43 45 65 77 89 98

این آموزش هم به پایان رسید.
موفق و پیروز باشید.

مطالعه بیشتر

مرتب سازی ادغامی (Merge Sort) در جاوا

الگوریتم مرتب سازی ادغامی (Merge Sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

الگوریتم مرتب سازی ادغامی (Merge Sort)

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

اشتراک گذاری در شبکه های اجتماعی