โปรแกรม Python สำหรับ Binary Insertion Sort

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

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

ที่นี่ ตามที่ชื่อบ่งชี้ เราใช้แนวคิดของ Binary Search ร่วมกับอัลกอริทึม Insertion Sort

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

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

# ฟังก์ชันจัดเรียง
def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        pos = binary_search(arr, temp, 0, i) + 1
        for k in range(i, pos, -1):
            arr[k] = arr[k - 1]
        arr[pos] = temp

def binary_search(arr, key, start, end):
    # กรณีฐาน
    if end - start <= 1:
        if key < arr[start]:
            return start - 1
        else:
            return start
    mid = (start + end) // 2
    if arr[mid] < key:
        return binary_search(arr, key, mid, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid)
    else:
        return mid

# โปรแกรมหลัก
arr = [1, 5, 3, 4, 8, 6, 3, 4]
n = len(arr)
insertion_sort(arr)
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 สำหรับ Binary Insertion Sort