Insertion Sort ใน Python

Insertion Sort: จัดเรียงโดยขยาย sorted array ทีละตัว เปรียบเทียบกับค่าสูงสุดใน sorted part ย้ายข้ามถ้าจำเป็น

อัลกอริทึม

• วนลูป input elements ขยาย sorted array ทีละรอบ
• เปรียบเทียบ current element กับค่าสูงสุดใน sorted array
• ถ้ามากกว่า คงที่ไว้ ถ้าน้อยกว่า หาตำแหน่งที่ถูกต้องใน sorted array และ shift ตัวที่มากกว่าไปขวา

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

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print("The sorted array is:")
for i in range(len(arr)):
    print(arr[i])

ผลลัพธ์

The sorted array is:
a i l o r t t u

Time Complexity: O(n²), Auxiliary Space: O(1)

สรุป

เรียนรู้ Insertion Sort ใน Python: สร้าง sorted array ทีละตัว shift ค่ามากกว่าไปขวา Time O(n²) Space O(1)