อัลกอริทึม Python

การเรียงแบบผสาน (merge sort) ใน Python

ในบทเรียนนี้ คุณจะเขียนการเรียงแบบผสานตามกลยุทธ์แบ่งแยกและเอาชนะ ด้วยฟังก์ชันเรียกตัวเอง

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

บทนำ

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

การเรียงแบบง่ายช้าลงมากเมื่อลิสต์โตขึ้น: ข้อมูลเพิ่มเป็นสองเท่าทำให้งานเพิ่มเป็นสี่เท่า 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)

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

  1. if len(values) <= 1: return values คือ base case ที่หยุดการเรียกซ้ำ
  2. merge_sort(values[:middle]) และ merge_sort(values[middle:]) เรียงสองครึ่ง
  3. ลูป while หยิบค่าด้านหน้าที่น้อยกว่าจาก left หรือ right จนลิสต์หนึ่งหมด
  4. left[left_index:] และ right[right_index:] เพิ่มค่าที่เหลือ ซึ่งเรียงอยู่แล้ว
  5. <= หยิบจากซ้ายก่อนเมื่อเท่ากัน ค่าที่เท่ากันจึงคงลำดับเดิม

ใช้เมื่อไร?

  • เรียงข้อมูลขนาดใหญ่ได้เร็วอย่างคาดเดาได้ ไม่มีกรณีแย่สุดที่เลวร้าย
  • เรียง linked list หรือข้อมูลที่ใหญ่เกินหน่วยความจำ (external sorting)
  • เรียนรู้ divide and conquer ซึ่งเป็นแพตเทิร์นที่ใช้ในอัลกอริทึมจำนวนมาก

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

  • โค้ด Python ทั่วไป: sorted() ใช้ Timsort อยู่แล้ว ซึ่งผสม merge sort กับ insertion sort อย่างลงตัว
  • หน่วยความจำจำกัดมาก: merge sort ต้องใช้พื้นที่เพิ่มสำหรับลิสต์ที่รวมแล้ว

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

O(n log n)

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

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

รันโค้ด →
main.py
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]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

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

[3, 9, 10, 27, 38, 43, 82]

อธิบายโค้ด

ฟังก์ชันเรียกตัวเองจะแบ่งลิสต์จนแต่ละส่วนเหลือสมาชิกตัวเดียว เพราะลิสต์ที่มีตัวเดียวเรียงแล้วเสมอ จากนั้นลูป while ผสานลิสต์ย่อยสองชุด โดยหยิบตัวที่เล็กกว่าระหว่างสมาชิกตัวแรกของทั้งสองเสมอ อัลกอริทึมทำงานใน O(n log n) เสมอและใช้หน่วยความจำเพิ่ม O(n)

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

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

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

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

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

ลืมส่วนที่เหลือ

เมื่อครึ่งหนึ่งหมด ส่วนที่เหลือของอีกครึ่งจะหายไป

ปัญหา
return result
วิธีแก้
return result + left[left_index:] + right[right_index:]

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

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

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

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

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