การเรียงแบบแทรก (insertion sort) ใน Python
ในบทเรียนนี้ คุณจะเขียนการเรียงแบบแทรก โดยแทรกแต่ละสมาชิกลงในตำแหน่งที่ถูกต้องของส่วนที่เรียงแล้ว
บทนำ
ปัญหาที่ต้องแก้
ข้อมูลมักมาแบบเกือบเรียงแล้ว หรือมาทีละรายการ: ลิสต์คะแนนที่เรียงแล้วได้คะแนนใหม่หนึ่งค่า การเรียงทั้งหมดใหม่นั้นสิ้นเปลือง 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) กับข้อมูลที่เกือบเรียงแล้ว
ประเด็นสำคัญ
for index in range(1, len(result)):เริ่มที่รายการที่สอง รายการเดียวถือว่าเรียงแล้วcurrentเก็บค่าที่กำลังแทรก ขณะที่ค่าที่ใหญ่กว่าเลื่อนไปwhile position >= 0 and result[position] > current:เลื่อนค่าที่ใหญ่กว่าแต่ละตัวไปทางขวาหนึ่งที่result[position + 1] = currentวางค่าลงในช่องว่างที่เปิดไว้
ใช้เมื่อไร?
- ลิสต์เล็กหรือลิสต์ที่เกือบเรียงแล้ว
- รักษาลิสต์ให้เรียงอยู่เมื่อมีรายการใหม่เข้ามา
- เป็นขั้นตอนสุดท้ายในการเรียงที่เร็วกว่า ซึ่งเปลี่ยนไปใช้ insertion sort กับชิ้นเล็กๆ
เมื่อไรยังไม่จำเป็น
- ลิสต์สุ่มขนาดใหญ่: การเลื่อนจะช้า ให้ใช้
sorted() - แทรกเข้าลิสต์ที่เรียงแล้วขนาดใหญ่บ่อยๆ:
bisect.insortหาตำแหน่งด้วย binary search
ภาพจำลอง การเรียงแบบแทรก (insertion sort) ใน Python
O(n²)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
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]))
ผลลัพธ์จากการรัน
[1, 3, 4, 5, 9]
อธิบายโค้ด
ตัวแปร current เก็บค่าที่จะแทรก ลูป while เลื่อนค่าที่มากกว่า current ไปทางขวาทีละหนึ่งตำแหน่งเพื่อเว้นที่ว่าง แล้ววาง current ลงในที่นั้น กรณีแย่ที่สุดความซับซ้อนเป็น O(n²) แต่กับข้อมูลที่เกือบเรียงแล้วจะใกล้ O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
เขียน 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
โจทย์ทั้งหมด