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

  • شنبه ۱۱ آبان ۱۳۹۸
  • بازدید ۴۰ نفر

merge sort algorithm 7328 تصویر

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

الگوریتم مرتب سازی ادغامی (Merge Sort) مانند الگوریتم QuickSort، به روش تقسیم و غلبه (Divide and Conquer) عمل می کند. در این الگوریتم آرایه داده شده به بخش های کوچک تر تقسیم می شود و هر بخش مرتب شده و بخش بعدی ادغام می شود تا در نهایت کل آرایه مرتب شد.

تابع merge برای ادغام دو بخش از آرایه مورد استفاده قرار می گیرد. merge(arr, l, m, r)  فرآیند کلیدی است که فرض می کند arr[l..m]  و arr[m+1..r] به صورت مرتب شده هستند و دو زیر آرایه مرتب شده را با هم ادغام می کند.

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

merge sort algorithm 7328 1 تصویر

پیاده سازی الگوریتم Merge Sort با استفاده از زبان برنامه نویسی C:

امتحان کنید

خروحی:

نکات

  • پیچیدگی زمانی در هر سه حالت (بدترین، متوسط، بهترین) برابر است merge sort algorithm 7328 2 تصویر
  • فضای اضافه برابر است با O(n).
  • این الگوریتم برای مرتب سازی لینک لیست ها با زمان O(nlogn) مناسب است.
ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است