การเรียงแบบผสาน (merge sort) ใน Python
ในบทเรียนนี้ คุณจะเขียนการเรียงแบบผสานตามกลยุทธ์แบ่งแยกและเอาชนะ ด้วยฟังก์ชันเรียกตัวเอง
บทนำ
ปัญหาที่ต้องแก้
การเรียงแบบง่ายช้าลงมากเมื่อลิสต์โตขึ้น: ข้อมูลเพิ่มเป็นสองเท่าทำให้งานเพิ่มเป็นสี่เท่า merge sort แบ่งโจทย์เป็นโจทย์ย่อยที่แก้ง่าย และทำให้งานโตเร็วกว่าข้อมูลเพียงเล็กน้อย
ลองนึกภาพแบบนี้
merge sort เหมือนการเรียงกระดาษข้อสอบกองใหญ่กับเพื่อนๆ คุณแบ่งกองเป็นครึ่ง ส่งแต่ละครึ่งต่อไป และพวกเขาแบ่งของตัวเองอีก จนทุกคนถือกระดาษแผ่นเดียว แล้วคนเป็นคู่ๆ รวมกองที่เรียงแล้วด้วยการหยิบแผ่นบนที่น้อยกว่าเสมอ จนเหลือกองที่เรียงแล้วกองเดียว
if len(values) <= 1:📄 กระดาษแผ่นเดียวถือว่าเรียงแล้วmerge_sort(values[:middle])✂️ แบ่งกองแล้วเรียงแต่ละครึ่งleft[left_index] <= right[right_index]🤝 รวม: หยิบแผ่นบนที่น้อยกว่าresult + left[left_index:] + right[right_index:]📚 เพิ่มส่วนที่เหลือของอีกกองmerge sort แบ่งลิสต์เป็นครึ่ง เรียงแต่ละครึ่งแบบเรียกซ้ำ และรวมสองครึ่งที่เรียงแล้ว ใช้เวลา O(n log n)
ประเด็นสำคัญ
if len(values) <= 1: return valuesคือ base case ที่หยุดการเรียกซ้ำmerge_sort(values[:middle])และmerge_sort(values[middle:])เรียงสองครึ่ง- ลูป
whileหยิบค่าด้านหน้าที่น้อยกว่าจากleftหรือrightจนลิสต์หนึ่งหมด left[left_index:]และright[right_index:]เพิ่มค่าที่เหลือ ซึ่งเรียงอยู่แล้ว<=หยิบจากซ้ายก่อนเมื่อเท่ากัน ค่าที่เท่ากันจึงคงลำดับเดิม
ใช้เมื่อไร?
- เรียงข้อมูลขนาดใหญ่ได้เร็วอย่างคาดเดาได้ ไม่มีกรณีแย่สุดที่เลวร้าย
- เรียง linked list หรือข้อมูลที่ใหญ่เกินหน่วยความจำ (external sorting)
- เรียนรู้ divide and conquer ซึ่งเป็นแพตเทิร์นที่ใช้ในอัลกอริทึมจำนวนมาก
เมื่อไรยังไม่จำเป็น
- โค้ด Python ทั่วไป:
sorted()ใช้ Timsort อยู่แล้ว ซึ่งผสม merge sort กับ insertion sort อย่างลงตัว - หน่วยความจำจำกัดมาก: merge sort ต้องใช้พื้นที่เพิ่มสำหรับลิสต์ที่รวมแล้ว
ภาพจำลอง การเรียงแบบผสาน (merge sort) ใน Python
O(n log n)กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น
โค้ดตัวอย่าง
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
ผลลัพธ์จากการรัน
[3, 9, 10, 27, 38, 43, 82]
อธิบายโค้ด
ฟังก์ชันเรียกตัวเองจะแบ่งลิสต์จนแต่ละส่วนเหลือสมาชิกตัวเดียว เพราะลิสต์ที่มีตัวเดียวเรียงแล้วเสมอ จากนั้นลูป while ผสานลิสต์ย่อยสองชุด โดยหยิบตัวที่เล็กกว่าระหว่างสมาชิกตัวแรกของทั้งสองเสมอ อัลกอริทึมทำงานใน O(n log n) เสมอและใช้หน่วยความจำเพิ่ม O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
ลืมส่วนที่เหลือ
เมื่อครึ่งหนึ่งหมด ส่วนที่เหลือของอีกครึ่งจะหายไป
return result
return result + left[left_index:] + right[right_index:]
เรียนบทนี้จบแล้วใช่ไหม
ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า
ฝึกด้วยโจทย์
ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI
โจทย์ทั้งหมด