อัลกอริทึม Python

การเรียงแบบแทรก (insertion sort) ใน Python

ในบทเรียนนี้ คุณจะเขียนการเรียงแบบแทรก โดยแทรกแต่ละสมาชิกลงในตำแหน่งที่ถูกต้องของส่วนที่เรียงแล้ว

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

ข้อมูลมักมาแบบเกือบเรียงแล้ว หรือมาทีละรายการ: ลิสต์คะแนนที่เรียงแล้วได้คะแนนใหม่หนึ่งค่า การเรียงทั้งหมดใหม่นั้นสิ้นเปลือง insertion sort จัดการกรณีนี้ได้ดีมาก และเป็นวิธีที่หลายคนเรียงไพ่ในมือ

ลองนึกภาพแบบนี้

insertion sort คือวิธีที่คุณเรียงไพ่ในมือ คุณหยิบไพ่ทีละใบแล้วเลื่อนไปทางซ้ายผ่านทุกใบที่ใหญ่กว่า จนมันอยู่ในที่ที่ถูกต้อง ไพ่ทางซ้ายของมันเรียงลำดับอยู่เสมอ

จากการเรียงไพ่สู่โค้ด
current = result[index]🃏 หยิบไพ่ใบถัดไป
result[position] > current👈 ใบทางซ้ายใหญ่กว่าไหม?
result[position + 1] = result[position]➡️ เลื่อนใบที่ใหญ่กว่าไปทางขวาหนึ่งที่
result[position + 1] = current📥 วางไพ่ลงในช่องว่าง
ส่วนซ้ายเรียงอยู่เสมอ รายการใหม่แต่ละตัวถูกแทรกเข้าไป
สรุปในประโยคเดียว

insertion sort สร้างส่วนที่เรียงแล้วทีละรายการ ด้วยการเลื่อนรายการที่ใหญ่กว่าไปทางขวาและแทรกรายการปัจจุบันลงในช่องว่าง เป็น O(n²) ในกรณีแย่สุด แต่ใกล้ O(n) กับข้อมูลที่เกือบเรียงแล้ว

ประเด็นสำคัญ

  1. for index in range(1, len(result)): เริ่มที่รายการที่สอง รายการเดียวถือว่าเรียงแล้ว
  2. current เก็บค่าที่กำลังแทรก ขณะที่ค่าที่ใหญ่กว่าเลื่อนไป
  3. while position >= 0 and result[position] > current: เลื่อนค่าที่ใหญ่กว่าแต่ละตัวไปทางขวาหนึ่งที่
  4. result[position + 1] = current วางค่าลงในช่องว่างที่เปิดไว้

ใช้เมื่อไร?

  • ลิสต์เล็กหรือลิสต์ที่เกือบเรียงแล้ว
  • รักษาลิสต์ให้เรียงอยู่เมื่อมีรายการใหม่เข้ามา
  • เป็นขั้นตอนสุดท้ายในการเรียงที่เร็วกว่า ซึ่งเปลี่ยนไปใช้ insertion sort กับชิ้นเล็กๆ

เมื่อไรยังไม่จำเป็น

  • ลิสต์สุ่มขนาดใหญ่: การเลื่อนจะช้า ให้ใช้ sorted()
  • แทรกเข้าลิสต์ที่เรียงแล้วขนาดใหญ่บ่อยๆ: bisect.insort หาตำแหน่งด้วย binary search

ภาพจำลอง การเรียงแบบแทรก (insertion sort) ใน Python

O(n²)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

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

รันโค้ด →
main.py
def insertion_sort(values):
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = current
    return result

print(insertion_sort([9, 5, 1, 4, 3]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

[1, 3, 4, 5, 9]

อธิบายโค้ด

ตัวแปร current เก็บค่าที่จะแทรก ลูป while เลื่อนค่าที่มากกว่า current ไปทางขวาทีละหนึ่งตำแหน่งเพื่อเว้นที่ว่าง แล้ววาง current ลงในที่นั้น กรณีแย่ที่สุดความซับซ้อนเป็น O(n²) แต่กับข้อมูลที่เกือบเรียงแล้วจะใกล้ O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

เขียน current กลับข้างในลูป

ค่าต้องถูกวางครั้งเดียว หลังจากค่าที่ใหญ่กว่าทั้งหมดเลื่อนไปแล้ว

ปัญหา
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    result[position] = current
    position -= 1
วิธีแก้
while position >= 0 and result[position] > current:
    result[position + 1] = result[position]
    position -= 1
result[position + 1] = current

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด