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

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

مقدمه

ما با این مطلب کمی از الگوریتم Merge Sort یا مرتب سازی ادغامی که مبتنی بر رویکرد تقسیم و غلبه است صحبت می کنیم، و سپس به پیاده سازی آن در پایتون می پردازیم.

Merge Sort یک الگوریتم “تقسیم و غلبه” است که در آن مسئله به زیرمسائل تقسیم شده و سپس برای غلبه به کل مسئله، راه حل ها ادغام می شوند. ما قبلاً هم درباره مرتب سازی ادغامی در اوپن مایند نوشته ایم که می توانید آن نوشته ها را در صفحات زیر مطالعه بفرمایید:

 

مرتب سازی ادغامی چیست

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

 

شیوه حل تقسیم و غلبه

 

  • آرایه به دو نیم تقسیم می شود و روند با هر نیمه تکرار می شود تا اینکه هر نیمه از اندازه ۱ یا ۰ باشد.
  • آرایه اندازه ۱ به صورت پیش فرض مرتب شده است، طبیعتاً دیگر آن را تقسیم نمی کنیم بلکه با یک آرایه دیگر به اندازه ۱ به طور مرتب ادغام می کنیم.
  • اکنون دو آرایه مرتب شده در یک آرایه بزرگ ترکیب شده اند. و این کار تا زمانی ادامه می یابد که همه عناصر ترکیب شده و آرایه مرتب شود.

در اینجا تصویری از مرتب سازی ادغامی برای روشن کردن روشن آن برای شما ارائه شده است.

آرایه ورودی = [۳،۱،۴،۱،۵،۹،۲،۶،۵،۴]

 

حال ، بیایید به سراغ پیاده سازی مرتب سازی ادغامی در پایتون برویم.

 

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

 

خروجی اجرای کد بالا به صورت زیر است:

 

فلوچارت پیاده سازی مرتب سازی ادغامی

در تصویر زیر فلوچارت مراحل اجرای کد بالا را مشاهده می کنید که به فهم کد کمک شایانی می کند.

فلوچارت برای کد پایتون مرتب سازی ادغامی

 

 

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

یکی از بهترین ویژگی های مرتب سازی ادغام تعداد کم مقایسه آن است. این الگوریتم O(n * log (n)) مقایسه را ایجاد می کند.

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

 

مطالعه بیشتر

می توانید مطالب زیر را در موضوع مرتب سازی مطالعه کنید.

الگوریتم مرتب سازی سریع یا Quick-sort

الگوریتم مرتب سازی انتخابی یا Selection Sort

الگوریتم مرتب سازی درجی یا Insertion sort

 

منبع استفاده شده برای این مطلب:

How to implement Merge Sort in Python?

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

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