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

جولای

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

مقدمه

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

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

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

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

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

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

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

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

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

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

def mergeSort(nlist):
    print("Splitting ",nlist)
    if len(nlist)>1:
        mid = len(nlist)//2
        lefthalf = nlist[:mid]
        righthalf = nlist[mid:]
 
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=j=k=0      
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                nlist[k]=lefthalf[i]
                i=i+1
            else:
                nlist[k]=righthalf[j]
                j=j+1
            k=k+1
 
        while i < len(lefthalf):
            nlist[k]=lefthalf[i]
            i=i+1
            k=k+1
 
        while j < len(righthalf):
            nlist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",nlist)
 
nlist = [3,1,4,1,5,9,2,6,5,4]
mergeSort(nlist)
print(nlist)

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

(‘Splitting ‘, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(‘Splitting ‘, [3, 1, 4, 1, 5])
(‘Splitting ‘, [3, 1])
(‘Splitting ‘, [3])
(‘Merging ‘, [3])
(‘Splitting ‘, [1])
(‘Merging ‘, [1])
(‘Merging ‘, [1, 3])
(‘Splitting ‘, [4, 1, 5])
(‘Splitting ‘, [4])
(‘Merging ‘, [4])
(‘Splitting ‘, [1, 5])
(‘Splitting ‘, [1])
(‘Merging ‘, [1])
(‘Splitting ‘, [5])
(‘Merging ‘, [5])
(‘Merging ‘, [1, 5])
(‘Merging ‘, [1, 4, 5])
(‘Merging ‘, [1, 1, 3, 4, 5])
(‘Splitting ‘, [9, 2, 6, 5, 4])
(‘Splitting ‘, [9, 2])
(‘Splitting ‘, [9])
(‘Merging ‘, [9])
(‘Splitting ‘, [2])
(‘Merging ‘, [2])
(‘Merging ‘, [2, 9])
(‘Splitting ‘, [6, 5, 4])
(‘Splitting ‘, [6])
(‘Merging ‘, [6])
(‘Splitting ‘, [5, 4])
(‘Splitting ‘, [5])
(‘Merging ‘, [5])
(‘Splitting ‘, [4])
(‘Merging ‘, [4])
(‘Merging ‘, [4, 5])
(‘Merging ‘, [4, 5, 6])
(‘Merging ‘, [2, 4, 5, 6, 9])
(‘Merging ‘, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]