โปรแกรม Python สำหรับ Recursive Insertion Sort (การจัดเรียงแบบแทรกแบบเรียกซ้ำ)

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

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

Insertion Sort ทำงานโดยการสร้างอาร์เรย์ขนานที่เราแทรกองค์ประกอบด้วยตนเองตามลำดับที่กำหนด

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

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

# วิธีแบบเรียกซ้ำ (recursive)
def insertionSortRecursive(arr, n):
    # กรณีฐาน (base case)
    if n <= 1:
        return
    # จัดเรียง n-1 องค์ประกอบแรก
    insertionSortRecursive(arr, n-1)
    last = arr[n-1]
    j = n-2
    # เลื่อนองค์ประกอบที่มากกว่า last ไปข้างหน้า
    while (j >= 0 and arr[j] > last):
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = last

# โปรแกรมหลัก
arr = [1, 5, 3, 4, 8, 6, 3, 4, 5]
n = len(arr)
insertionSortRecursive(arr, n)
print("Sorted array is:")
for i in range(n):
    print(arr[i], end=" ")

ผลลัพธ์

Sorted array is : 1 3 3 4 4 5 5 6 8

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

สรุป

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