منبع اصلی نوشتار زیر در این لینک قرار دارد

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

مقدمه

در ادامه معرفی الگوریتم های مرتب سازی معروف از اوپن مایند، حالا مرتب سازی ادغامی یا  Merge Sort را به شما آموزش می دهیم.

قبل از این که به ادامه بحث بپردازیم، مطالب الگوریتم های مرتب سازی را که منتشر کرده ایم را بار دیگر معرفی می کنم:

 

شرح الگوریتم مرتب سازی ادغامی

مرتب سازی ادغامی از شیوه بازگشتی برای حل مسئله مرتب سازی استفاده می کند که از بسیاری الگوریتم های مرتب سازی مقایسه ای دیگر بهینه تر است. به طور دقیق تر، مرتب سازی ادغامی با تکنیک تقسیم و حل طراحی شده است.

پس با در نظر گرفتن مفاهیم بازگشتی و تقسیم و حل، باید بدانید که روش کار به این صورت است که ما تمام آرایه را دو بخش تقسیم می کنیم و سپس:

  • بخش چپ را مرتب می کنیم (بازگشتی با تقسیم های مجدد)
  • بخش راست را مرتب می کنیم (بازگشتی با تقسیم های مجدد)
  • دو بخش مرتب شده را با هم ادغام می کنیم

 

مثالی از مرتب سازی ادغامی

به درخت زیر که مراحل کار الگوریتم مرتب سازی ادغامی را نشان می دهد، دقت کنید:

نمونه ای از درخت اجرای بازگشتی الگوریتم مرتب سازی ادغامی

نمونه ای از درخت اجرای بازگشتی الگوریتم مرتب سازی ادغامی

 

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

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

در مثال بالا، ما آرایه

3 5 4 2 1
را داریم که در مرحله اول به دو بخش
3 5 4
و
2 1
شکسته می شود. برای مرتب سازی آنها ما تقسیم را ادامه می دهیم تا زمانی که داخل هر زیربخش از آرایه، تنها یک عنصر باقی بماند که این حالت پایانی فراخوانی های بازگشتی است (برگ های درخت در تصویر بالا).

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

پیاده سازی مرتب سازی ادغامی

بیایید به سراغ پیاده سازی با جاوا برویم.

کد مرتب سازی ادغامی به دو بخش در دو تابع تقسیم می شود. تابع اولی (تابع اصلی هم هست) همان کار سه مرحله ای را که پیشتر توضیح دادیم فراخوانی می کند، یعنی تقسیم به بخش چپ و راست و ادغام مقدار برگشتی حاصل از فراخوانی های چپ و راست.

پس آرایه به همراه شماره عناصر محدوده  چپ تا راست(انتها و ابتدا) را به تابع اصلی می دهیم تا بر اساس آنها دو بخش ایجاد کند و فراخوانی های بازگشتی را روی آنها انجام دهد. در اولین فراخوانی تابع اصلی، بدیهی است که مقادیر محدود چپ و راست،

 و 
array.length-1
خواهد بود.

تابع دوم هم برای ادغام به صورت مرتب است که کمی بعد بیشتر درباره آن خواهید خواند. اما حالا به همان تابع اصلی بپردازیم.

حالت پایه برای فراخوانی بازگشتی، خالی بودن آرایه وارد شده است. زمانی که در آخرین مرحله سعی کنید آرایه یک عضوی را هم بشکنید و به دو نیمه تقسیم کنید، آنگاه آرایه ای که فراخوانی بعدی تحویل می دهید عضوی ندارد و تهی است. اگر هم چنین شود محدوده چپ و راست زیرآرایه روی هم می افتند که به این صورت بررسی شده:

if (right <= left) return;

البته همانطور که دیدید، در تصویر بالا، دو زیرآرایه تهی در انتهای هر برگ را رسم نکرده ایم، که این برای حفظ سادگی بوده است.

پیاده سازی در جاوا

پیاده سازی تابع اصلی با نام

mergeSort
را در زیر می بینید:

public static void mergeSort(int[] array, int left, int right) {
    if (right <= left) return;
    int mid = (left+right)/2;
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);
    merge(array, left, mid, right);
}

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

پس از کپی زیرآرایه ها از آرایه اولیه به فضاهای موقت جدید، ما از ابتدای محدوده شروع می کنیم و هر بار کوچکترین عضو بین اعضای دو زیرآرایه مذکور را انتخاب می کنیم و روی آرایه اصلی می نویسیم و یکی جلوتر می رویم.

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

به کد زیر نگاهی بیاندازید تا این توضیحات را در قالب کد جاوا ببینید و برایتان واضح شوند:

void merge(int[] array, int left, int mid, int right) {
    // calculating lengths
    int lengthLeft = mid - left + 1;
    int lengthRight = right - mid;

    // creating temporary subarrays
    int leftArray[] = new int [lengthLeft];
    int rightArray[] = new int [lengthRight];

    // copying our sorted subarrays into temporaries
    for (int i = 0; i < lengthLeft; i++)
        leftArray[i] = array[left+i];
    for (int i = 0; i < lengthRight; i++)
        rightArray[i] = array[mid+i+1];

    // iterators containing current index of temp subarrays
    int leftIndex = 0;
    int rightIndex = 0;

    // copying from leftArray and rightArray back into array
    for (int i = left; i < right + 1; i++) {
        // if there are still uncopied elements in R and L, copy minimum of the two
        if (leftIndex < lengthLeft && rightIndex < lengthRight) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
                array[i] = leftArray[leftIndex];
                leftIndex++;
            }
            else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        }
        // if all the elements have been copied from rightArray, copy the rest of leftArray
        else if (leftIndex < lengthLeft) {
            array[i] = leftArray[leftIndex];
            leftIndex++;
        }
        // if all the elements have been copied from leftArray, copy the rest of rightArray
        else if (rightIndex < lengthRight) {
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

 

درجه زمانی مرتب سازی ادغامی

برای به دست آوردن درجه زمانی مرتب سازی ادغامی باید کمی دست به ریاضیات شویم!

به سراغ قضیه اصلی تحلیل الگوریتم ها می رویم. ابتدا حالت های قضیه اساسی را ذکر می کنیم و سپس با نوشتن و بررسی رابطه بازگشتی مرتب سازی ادغامی، درجه زمانی O بزرگ را به دست می آوریم.

اگر رابطه بازگشتی تعریف یک الگوریتم به صورت زیر باشد :

شکل کلی رابطه بازگشتی

شکل کلی رابطه بازگشتی

 

آنگاه، قضیه اصلی بیان می کند که درجه زمانی برای این رابطه به صورت زیر تعریف می شود:

درجه زمانی برای رابطه بازگشتی طبق قضیه اصلی تحلیل الگوریتم ها

درجه زمانی برای رابطه بازگشتی طبق قضیه اصلی تحلیل الگوریتم ها

 

خب، حالا که رابطه بازگشتی مرتب سازی ادغامی به صورت زیر است:

رابطه بازگشتی مرتب سازی ادغامی

رابطه بازگشتی مرتب سازی ادغامی

 

 

با در نظر گرفتن a=2 و b=2 و f(n)=cn و k=1 داریم حالت دوم از رابطه قضیه اصلی اینجا صادق است و به این نتیجه می رسیم که درجه زمانی مرتب سازی ادغامی برابر با O(nlog n) است.

 

 

مرجع نگارش این مطلب آموزشی، مطلب آنلاین دیگری با عنوان “Sorting Algorithms in Java” بوده است.

نوشته الگوریتم مرتب سازی ادغامی یا Merge Sort اولین بار در اوپن مایند. پدیدار شد.



برچسب ها :