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

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับการนำ Insertion Sort ไปใช้งานใน Python 3.x หรือเวอร์ชันก่อนหน้า

อัลกอริทึม

1. วนลูปผ่านอินพุตโดยเพิ่มอาร์เรย์ที่เรียงแล้วในแต่ละรอบ
2. เปรียบเทียบองค์ประกอบปัจจุบันกับค่าสูงสุดในอาร์เรย์ที่เรียงแล้ว
3. ถ้าองค์ประกอบปัจจุบันมากกว่า ให้ทิ้งไว้ที่เดิมและไปตัวถัดไป มิฉะนั้น หาตำแหน่งที่ถูกต้องในอาร์เรย์ที่เรียงแล้วและย้ายไปที่ตำแหน่งนั้น
4. ทำได้โดยการเลื่อนองค์ประกอบที่มากกว่าองค์ประกอบปัจจุบันในอาร์เรย์ที่เรียงแล้ว ไปขวาหนึ่งตำแหน่ง

ตอนนี้มาดูการแสดงภาพของอัลกอริทึม

ตอนนี้มาดูการนำไปใช้งาน

ตัวอย่าง

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # ย้ายองค์ประกอบของ arr[0..i-1] ที่มากกว่า key
        # ไปหนึ่งตำแหน่งข้างหน้าตำแหน่งปัจจุบัน
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# main
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 3.x หรือเวอร์ชันก่อนหน้า