مرتب سازی ادغامی در پایتون (Merge Sort)

در این جلسه به آموزش مرتب سازی ادغامی در پایتون می‌پردازیم. پیش نیازهای این جلسه شامل موارد زیر است:

1. آشنایی با حلقه While
2. آشنایی با تابع
3. آشنایی با if
4. آشنایی با روش بازگشتی
5. آشنایی با لیست

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

 مرتب‌سازی ادغامی یک الگوریتم مرتب‌سازی تطبیقی با زمان اجرای nlogn می‌باشد. در اکثر پیاده‌سازی‌ها این الگوریتم پایدار می‌باشد. بدین معنی که این الگوریتم ترتیب ورودی‌های مساوی را در خروجی مرتب شده حفظ می‌کند. این یک مثال از الگوریتم تقسیم و تسخیر می‌باشد. این الگوریتم در سال ۱۹۴۵ توسط جان فون نویمان اختراع شده‌است.

از نظر مفهومی یک الگوریتم مرتب‌سازی ادغام بدین صورت کار می‌کند:

1. اگر طول لسیت ۰ یا ۱ باشد آن پیش از این مرتب شده‌است در غیر این صورت
2. لیست نامرتب را به دو زیرلیست که اندازه آن‌ها در حدود نصف سایز لیست اولیه‌است تقسیم می‌کند.
3. هر زیرلیست را به طور بازگشتی با صدا کردن merge sort مرتب می‌کند.
4. دو تا دوتا زیر لیست‌ها را از آخر ادغام می‌کند تا به یک لیست برسد

مرتب‌سازی ادغام ۲ ایده اصلی را با هم ترکیب می‌کند تا زمان اجرایش تقویت شود

1. یک لیست کوچک از گام‌های کم‌تری برای مرتب‌کردن نسبت به یک لیست بزرگ استفاده می‌کند.
2. برای مرتب کردن دو لیست مرتب‌شده نسبت به دو لیست نامرتب گام‌های کمتری نیاز می‌باشد به عنوان مثال اگر این لیست‌ها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبار پیمایش کنید(ویکیپدیا)

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

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

ما وقتی دو لیست مرتب داریم و می‌خواهیم آنها را با هم ادغام(merge) کنیم باید دو اندیس به ابتدای هر دو لیست اشاره کند. ما این اندیس ها را i و  j می‌نامیم. سپس کوچکترین مقداری که در اندیس های i و j قرار دارد را برمیداریم و اندیس مورد نظر را یکی به جلو حرکت می‌دهیم. با این کار ما بین دو لیست کوچکترین مقدار را برمیداریم.

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

def mergeSort(arr): 
    if len(arr) >1: 
        mid = len(arr)//2 # Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 
  
        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 
  
        i = j = k = 0
          
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
            k+= 1
          
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
          
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1

کد مرتب سازی ادغامی در پایتون لیست ورودی را نصف می‌کند و دو لیست کوچکتر را مرتب می‌کند سپس به ادغام دو لیست مرتب ایجاد شده می‌پردازد. در حقیقت ما دو لیست به نام L و R تعریف کرده‌ایم که لیست‌های کوچک شده ما هستند و ابتدا این دو لیست را مرتب می‌کنیم سپس آنها را ادغام می‌کنیم(حلقه while اول) در صورتی که بعد از ادغام عنصری در هر کدام از لیست‌ها باقی مانده باشد آنها را نیز به لیست اصلی خود وارد می‌کنیم. حلقه While دوم و سوم برای ما این کار را انجام می‌دهند.

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

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

def printList(arr): 
    for i in range(len(arr)):         
        print(arr[i], end =" ") 
    print() 
if __name__ == '__main__':
        arr = [12, 11, 13, 5, 6, 7]  
        print ("Given array is", end ="\n")  
        printList(arr) 
        mergeSort(arr) 
        print("Sorted array is: ", end ="\n") 
        printList(arr) 

خروجی مرتب سازی ادغامی در پایتون به صورت زیر است:

Given array is

12 11 13 5 6 7

Sorted array is:

5 6 7 11 12 13

ویدئو آموزش