โปรแกรม Python สำหรับ Iterative Merge Sort (Merge Sort แบบวนรอบ)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดอาร์เรย์ ให้จัดเรียงโดยใช้แนวคิดของ Merge Sort แบบวนรอบ (iteration)

ที่นี่เราจะวางองค์ประกอบสูงสุดไว้ที่ท้าย สิ่งนี้จะทำซ้ำจนกว่าอาร์เรย์จะถูกจัดเรียง

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

# วิธีแบบวนรอบ (iterative)
def mergeSort(a):
    current_size = 1
    # วนลูปผ่าน subarrays
    while current_size < len(a) - 1:
        left = 0
        # subarray ที่กำลังจัดเรียง
        while left < len(a)-1:
            # คำนวณค่ากลาง (mid)
            mid = left + current_size - 1
            # คำนวณ right
            right = ((2 * current_size + left - 1, len(a) - 1)[2 * current_size + left - 1 > len(a)-1])
            # Merge
            merge(a, left, mid, right)
            left = left + current_size * 2
        # เพิ่มขนาด subarray
        current_size = 2 * current_size

# ฟังก์ชัน Merge
def merge(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]
    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1
    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1
    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1

# โค้ดทดสอบ
a = [2, 5, 3, 8, 6, 5, 4, 7]
mergeSort(a)
print("Sorted array is:")
for i in range(len(a)):
    print(a[i], end=" ")

ผลลัพธ์

Sorted array is 2 3 4 5 5 6 7 8

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Iterative Merge Sort