python, پایتون, ساختمان داده در پایتون, مرتب سازی در پایتون

مرتب سازی ادغامی در پایتون (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

ویدئو آموزش

پسورد فایل: www.codegate.ir

نوشته های مشابه

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

  1. ابراهیمی گفت:

    سلام، وقت بخیر. ببخشید امکانش هست برنامه ی مرتب سازی ادغامی رو بدون استفاده از توابع و کلاس ها در زبان c++ بذارید؟ ممنون

    1. سعید غریبی گفت:

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

      1. ابراهیمی گفت:

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

        1. سعید غریبی گفت:

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

          1. ابراهیمی گفت:

            واقعا ممنونم ازتون که جواب می دین. الان استاد ما گفتن الگوریتم مرتب سازی ادغامی رو بدون استفاده از تابع و کلاس ها در زبان c++ پیاده سازی کنید. ازشون که پرسیدم میگن پیاده سازی این برنامه بدون استفاده از توابع و کلاس ها امکان پذیره. نمی دونم باید چی کار کنم.

          2. سعید غریبی گفت:

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

  2. Parsa گفت:

    با سلام و احترام
    لطفا راهنمایی کنید چرا به جای این الگوریتم، از دستور merge sort برای کل آرایه استفاده نمی کنیم.
    آیا تنها بهاین دلیل که استفاده از این الگوریتم زمان محاسبات را کاهش میدهد؟

    1. سلام. وقت بخیر. در کد پیاده سازی شده در این قسمت از روش بازگشتی استفاده شده است. روش های غیر بازگشتی نیز وجود دارد که با کمک حلقه ها پیاده سازی می گردد. دلیل استفاده از روش بازگشتی در این الگوریتم راحتی پیاده سازی بوده است. سرعت الگوریتم در هر دو حالت n*logn است و فضای حافظه که برای مرتب سازی می گیرد n می باشد که n همان طول آرایه است.
      در زمینه سوال شما باید بگویم بله اگر merge sort بر روی کل آرایه صدا زده شود هزینه زمانی که برای مرتب سازی انجام می گیرد به مراتب بیشتر خواهد شد.

دیدگاهتان را بنویسید

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