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

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

مقدمه

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

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

 

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

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

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

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

 

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

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

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

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

 

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

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

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

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

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

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

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

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

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

حالت پایه برای فراخوانی بازگشتی، خالی بودن آرایه وارد شده است. زمانی که در آخرین مرحله سعی کنید آرایه یک عضوی را هم بشکنید و به دو نیمه تقسیم کنید، آنگاه آرایه ای که فراخوانی بعدی تحویل می دهید عضوی ندارد و تهی است. اگر هم چنین شود محدوده چپ و راست زیرآرایه روی هم می افتند که به این صورت بررسی شده: if (right <= left) return;

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

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

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

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

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

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

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

 

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

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

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

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

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

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

 

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

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

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

 

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

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

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

 

 

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

 

 

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

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *