«مرتب سازی ادغامی» (Merge Sort) الگوریتمی کارآمد، پایدار و مبتنی بر مقایسه است که برای مرتب‌سازی داده‌ها به‌کار می‌رود. این الگوریتم به علت پیچیدگی زمانی O(n log n) – پارامتر n طول آرایه است – چه در بدترین حالت عملکرد و چه در حالت میانگین عملکردی خود مورد تحسین واقع شده است. این الگوریتم برای حل مسئله‌ها از تکنیک «تقسیم و حل» (Divide-And-Conquer) استفاده می‌کند. در این رویکرد حل مسئله، مسائل بزرگ را تا حد ممکن به زیرمسائل کوچک‌تر و هم اندازه تقسیم می‌کنند. تا جایی که هر زیر مسئله به‌سادگی قابل حل باشد. با اینکه الگوریتم مرتب سازی ادغامی جز الگوریتم‌های پیچیده‌ای محسوب نمی‌شود، اما درک آن به شناسایی فاکتورهایی که در الگوریتم‌های کارآمد‌تر موثر هستند، کمک می‌کند. شناخت فاکتورهای مهم در انتخاب صحیح بین الگوریتم‌های پیچیده‌تر برای حل مسائل مربوط به داده‌ها تاثیر بسزایی دارد. این الگوریتم در سال ۱۹۴۵ توسط «جان فون نویمان» (John Von Neumann) ایجاد شد و بر اساس رویکرد «تقسیم و تسخیر» یا «تقسیم و حل» (Divide-And-Conquer) توسعه داده شد.

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

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

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

این روند تقسیم، حل و ادغام راه حلی را برای مسئله موجود ارائه می‌دهد.

مثال

آرایه نامرتب [2, 5, 1, 3]  را در نظر بگیرید. الگوریتم مرتب سازی ادغامی کار را با تقسیم این آرایه به زیر آرایه‌هایی شروع می‌کند که هر کدام در کمترین حالت شامل یک عنصر – [1]  و [2] و [3] و [5] - می‌شوند. سپس شروع به ادغام زیر‌لیست‌ها به صورتی می‌کند که مرتب در کنار هم قرار بگیرند. در نهایت به آرایه مرتب شده [ 1, 2, 3, 5 ] می رسد.

تعریف

دو عملیات اصلی این الگوریتم شامل رفتارهای «تقسیم» و «حل» می‌شود. مرحله «تقسیم» مربوط به زمانی می‌شود که آرایه به دو نیمه تقسیم شده است. در حالی که مرحله «حل یا تسخیر» مربوط به زمانی است که نیمه‌های مرتب شده به صورت مجزا از یکدیگر را در کنار هم قرار می‌دهیم. در بخش‌های بعدی، این دو قدم اصلی الگوریتم را به صورت کامل‌تری توضیح داده‌ایم.

چگونه بر روی مبحث الگوریتم ها تسلط پیدا کنیم؟

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

در این بخش چند مورد از فیلم‌هی آموزشی مربوط به ساختمان داده و طراحی الگوریتم را معرفی کرده‌ایم. در صورت تمایل با کلیک بر روی تصویر بالا می‌توانید به صفحه اصلی این مجموعه آموزشی رفته و سایر فیلم‌ها را نیز مرور و بررسی کنید.

روش تقسیم و حل الگوریتم مرتب سازی ادغامی چگونه است؟

برای اینکه الگوریتم مرتب سازی ادغامی را درک کنیم باید با پارادایم‌ روش «تقسیم و حل» در کنار مفهوم برنامه‌نویسی رفتارهای بازگشتی آشنا شویم. رفتارهای «بازگشتی» (Recursion)، در دنیای علوم کامپیوتر به فرایندی می‌گویند که روشی در درون خودش برای حل مسئله کمک می‌گیرد.

به عبارت دیگر، تابع می‌تواند به صورت تکراری خود را فراخوانی کند.

الگوریتم‌های «تقسیم و حل» – که الگوریتم مرتب سازی ادغامی هم نوعی از آن‌ها است – از تکنیک توابع بازگشتی برای حل مسائل مشخص شده استفاده می‌کنند. الگوریتم‌های «تقسیم و حل» مسائل پیچیده را به بخش‌های کوچکتری تجزیه می‌کنند. یعنی جایی که راه حل تعریف شده به صورت بازگشتی بر روی هر کدام از بخش‌های تجزیه شده اعمال می‌شود. هر کدام از این بخش‌های کوچک زیر مجموعه مربوط به مسئله اصلی و بزرگ به صورت جداگانه حل می‌شوند. سپس راه حل‌های آماده به صورت منظم با یکدیگر ترکیب شده و مسئله اصلی را حل می‌کنند.

رویکرد «تقسیم و حل» (Divide-And-Conquer) برای طراحی الگوریتم، سه عنصر اصلی و اولیه را با یکدیگر ترکیب می‌کند.

• تجزیه مسئله بزرگتر به زیرمسائل کوچکتر (تقسیم)
• استفاده بازگشتی از توابع برای حل کردن هر کدام از زیرمسائل کوچکتر (حل)
• راه حل نهایی از ترکیب راه حل‌های مربوط به زیرمسائل کوچک مربوط به مسئله بزرگ‌تر تشکیل می‌شود.

الگوریتم‌های دیگری هم مانند «مرتب‌سازی سریع» (Quicksort)، «جست‌وجوی دودویی» (Binary Search) و «الگوریتم استراسن»(Strassen’s Algorithm) نیز از تکنیک تقسیم و حل در روند حل مسئله خود استفاده می‌کنند.

مراحل حل و پیاده سازی

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

1. تقسیم
2. حل
3. ادغام

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

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

در تصویر زیر، می‌توانید تمام عملیات تقسیم، مقایسه و ترکیب را ببینید. این قدم‌ها به ترتیب در الگوریتم مرتب سازی ادغامی شامل می‌شوند.

تصویر بالا مربوط به مرحله اول و تقسیم لیست داده شده در مسئله است. اما تصویر پایین فرایند مقایسه و ترکیب را برای ساخت لیست نهایی جواب نشان می‌دهد.

یکی از موارد کاربردی الگوریتم مرتب‌سازی ادغامی در زمان مرتب‌سازی لیست‌های پیوندی است که در این مطلب به آن اشاره شده. اما برای اینکه با لیست‌های پیوندی در ساختمان داده آشنا شده و موضوع را بهتر درک کنید پیشنهاد می‌کنیم که مطلب لیست پیوندی در ساختمان داده چیست؟ توضیح به زبان ساده را از مجله فرادرس مطالعه کنید.

برای اینکه خودمان این الگوریتم را پیاده‌سازی کنیم باید قدم به قدم طبق اصول و قواعد مطرح شده در پایین اقدام کنیم.

• در ابتدا تابعی به نام merge_sort می‌سازیم که به عنوان آرگومان، لیستی از اعداد صحیح را بپذیرد. تمام دستور‌العمل‌های بعدی که در ادامه ارائه شده‌اند درون این تابع اجرا می‌شوند. بنابراین باید در همین تابع هم پیاده‌سازی شوند.
• با تقسیم کردن لیست به دو نیم شروع می‌کنیم. باید اندازه اولیه لیست را ثبت و ذخیره کنیم.
• بررسی می‌کنیم که آیا اندازه ذخیره شده برابر یا ‍1 است یا نه. اگر شرط ارزیابی شده جواب True برگرداند، خود لیست را برمی‌گردانیم. این عمل به معنای این است که فقط یک عنصر در لیست باقی مانده. بنابراین دیگر نیازی به تقسیم کردن لیست نداریم.
• نقطه میانی لیستی که تعداد عناصر آن بزرگ‌تر از ‍1 است را پیدا می‌کنیم. در زمان استفاده از زبان برنامه نویسی پایتون با کمک عملگر // برای تقسیم در پایتون، عملیات تقسیم را می‌توان با حذف مقدار باقیمانده از جواب انجام داد. این عملگر، نتیجه تقسیم را به سمت اولین عدد صحیح رند می‌کند یا در واقع باقیمانده را حذف می‌کند. به این تقسیم، «تقسیم صحیح» (Floor Division) هم گفته می‌شود.
• با استفاده از نقطه میانی لیست به عنوان محل رجوع، لیست را به دو نیم تقسیم می‌کنیم. تا اینجای کار جنبه تقسیم را از چهارچوب عملیاتی الگوریتم «تقسیم و حل» انجام دادیم.
• در این مرحله برای ساده‌سازی عملیات تقسیم لیست‌ها به زیر‌لیست‌هایی تقریبا مساوی از تکنیک بازگشتی استفاده می‌کنیم. نتایج فراخوانی تابع merge_sort به متغیرهای left_half و right_half تخصیص داده می‌شود. هر کدام از نیمه‌های تشکیل شده از لیست اولیه دوباره به عنوان پارامتر به تابع merge_sort ارسال می‌شوند.
• تابع merge_sort به عنوان مقدار بازگشتی، فراخوانی تابعی را برمی‌گرداند که دو لیست کوچکتر را باهم ادغام می‌کند. در نتیجه این عملیات ادغام، لیستی ترکیب شده و مرتب برمی‌گردد.

1def merge_sort(list: [int]):
2    list_length = len(list)
3    
4    if list_length == 1:
5        return list
6    
7    mid_point = list_length // 2
8    
9    left_half = merge_sort(list[:mid_point])
10    right_half = merge_sort(list[mid_point:])
11    
12    return merge(left_half, right_half)

• سپس تابعی به نام merge ایجاد می‌کنیم. این تابع دو لیست از اعداد Integer را به عنوان آرگومان می‌پذیرد. تابع merge قرار است شامل دو جنبه «حل» و «ترکیب» از الگوریتم مرتب سازی ادغامی شود. همه مراحلی که در ادامه می‌آیند در داخل این تابع پیاده‌سازی شده‌اند.
• لیستی خالی را به متغیری به نام output تخصیص می‌دهیم. این لیست مقادیر اعداد صحیح مرتب شده را نگهمی‌دارد.
• نشانگرهای i و j برای ایندکس‌گذاری به ترتیب لیست‌های چپ و راست استفاده می‌شوند.
• درون حلقه while پایتون، فرایند مقایسه‌ای بین عناصر لیست‌های چپ و راست جریان دارد. بعد از هر مقایسه، لیست output با دو مقدار مقایسه شده پر می‌شود. نشانگر مربوط به لیستی که عناصر به آن اضافه شده‌اند – در اینجا با استفاده از تابع append در پایتون – افزایش پیدا می‌کند.
• عناصر باقی مانده‌ای که باید به لیست مرتب شده اضافه شوند، عناصری هستند که از مقدار نشانگر فعلی تا انتهای لیست مربوط قرار می‌گیرند.

1def merge(left, right):
2    output = []
3    i = j = 0
4    
5    while (i < len(left) and j < len(right)):
6        if left[i] < right[j]:
7            output.append(left[i])
8            i +=1
9        else:
10            output.append(right[j])
11            j +=1
12    output.extend(left[i:])
13    output.extend(right[j:])
14    
15    return output
16    
17unsorted_list = [2, 4, 1, 5, 7, 2, 6, 1, 1, 6, 4, 10, 33, 5, 7, 23]
18sorted_list = merge_sort(unsorted_list)
19print(unsorted_list)
20print(sorted_list)

کارآمدی و پیچیده گی مرتب سازی ادغامی

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

نشانگر حرف O بزرگ انگلیسی، استانداری برای تعریف و سازماندهی عملکرد الگوریتم‌ها است. از این استاندارد برای تعیین بهره‌وری زمان اجرا و میزان حافظه مورد نیاز الگوریتم‌ها استفاده می‌شود.

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

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

مرحله «حل» شامل تقسیم کردن و حل زیرآرایه‌ها به روش بازگشتی است. این مرحله را با نماد «log n» علامت گذاری می‌کنند. مرحله «ترکیب» شامل ترکیب‌کردن نتایج برای رسیدن به لیست نهایی می‌شود. زمان اجرای این عملیات بسته به اندازه لیست است. بنابراین با نماد O(n) نشان داده می‌شود.

در نهایت نمادگذاری پیچیده‌گی زمانی الگوریتم مرتب‌سازی ادغامی برابر با «log n * n * O(1)» است. در «علامت‌گذاری با حرف O بزرگ» (Big O notation) ثابت‌ها و شرایط سطح پایین قابل چشم‌پوشی هستند. به این معنا که نمادگذاری نهایی برای پیچیدگی زمانی الگوریتم مرتب سازی ادغامی برابر با «O(n log n)» است.

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

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

کارآمدی

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

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

پایداری

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

چطور با فرادرس برنامه نویس شویم؟

برنامه‌نویسی یکی از جذاب‌ترین رشته‌های علمی و شغلی در اواخر قرن بیستم و کل قرن بیست‌ یکم تا به امروز بوده است. بسیاری از افراد، هم به‌خاطر علاقه و سرگرمی و هم به‌خاطر مسائل شغلی به یادگیری برنامه‌نویسی مشغول شده‌اند. در این شغل محدودیت‌های جسمی، جنسیتی و سنی اثر گذار نیستند. خود رشته برنامه‌نویسی شامل تکنولوژی‌های بسیار متنوعی است و هر زبان برنامه نویسی مزیت‌ها و توانایی‌های خود را دارد. وب‌سایت آموزشی فرادرس برای یادگیری برنامه‌نویسی متناسب با همه سنین و همه سطوح علمی مخاطبان، فیلم‌های آموزشی متنوعی تولید کرده است. هر زبان برنامه‌نویسی برای خود گرایش‌ها و تکنولوژی‌های خاصی دارد که بسته به فعالیت جامعه برنامه‌نویسان آن زبان توسعه داده شده‌اند. در فرادرس تلاش کردیم تقریبا همه این گرایش‌ها و تکنولوژی‌های متنوع را برای کمک به علاقه‌مندان به تکنولوژی با بهترین کیفیت ممکن پوشش دهیم.

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

جمع بندی

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

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

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