مقدمه
در ادامه معرفی الگوریتم های مرتب سازی معروف از اوپن مایند، حالا مرتب سازی ادغامی یا Merge Sort را به شما آموزش می دهیم.
قبل از این که به ادامه بحث بپردازیم، مطالب الگوریتم های مرتب سازی را که منتشر کرده ایم را بار دیگر معرفی می کنم:
- مفهوم مرتب سازی
- Bubble sort
- Insertion sort
- Selection Sort
- Merge sort
- Quick sort
- Heap sort
- Distribution sorts
- Concurrent sorts
- Counting 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 اولین بار در اوپن مایند. پدیدار شد.