Merge sort

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

Merge sort

ใช้หลักการ แบ่งแล้วเอาชนะ
- แบ่ง (Divide)
  - แบ่งปัญหาออกเป็นปัญหาย่อย
- เอาชนะ (Conquer)
  - แก้ปัญหาย่อยแบบ recursive
- รวม (Combine)
  - รวมผลลัพธ์ของปัญหาย่อยเพื่อได้คำตอบสุดท้าย

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ โดยรายการถูกแบ่งออกเป็นสองส่วน

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ รายการถูกแบ่งเป็นสองส่วน โดยรายการใหม่แรกมีครึ่งซ้าย และรายการใหม่ที่สองมีครึ่งขวาของรายการต้นฉบับ

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ รายการใหม่ถูกแบ่งออกเป็นสองส่วนอีกครั้ง

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ พร้อมรายการใหม่จากการแบ่งรายการล่าสุด

Merge sort - in action

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ รายการใหม่ถูกแบ่งออกเป็นสองส่วน

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ องค์ประกอบจากรายการย่อยสุดท้ายถูกเรียงลำดับแล้ว

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ องค์ประกอบจากรายการย่อยสุดท้ายถูกรวมและเรียงลำดับแล้ว

Merge sort - ตัวอย่างการทำงาน

ภาพแสดงรายการที่มีตัวเลขไม่เรียงลำดับ องค์ประกอบทั้งหมดถูกรวมและเรียงลำดับครบถ้วนแล้ว

Merge sort - การนำไปใช้งาน

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge sort - ความซับซ้อน

กรณีแย่ที่สุด: $O(n\log{}n)$
- ดีกว่า bubble sort, selection sort และ insertion sort อย่างมีนัยสำคัญ
- เหมาะสำหรับการเรียงลำดับรายการขนาดใหญ่
กรณีเฉลี่ย: $\Theta(n\log{}n)$
กรณีดีที่สุด: $\Omega(n\log{}n)$
- อัลกอริทึมอื่น (เช่น bubble sort, insertion sort) มี complexity กรณีดีที่สุดที่ดีกว่า
Space complexity: $O(n)$
- ใช้พื้นที่มากกว่าอัลกอริทึมที่มี $O(1)$
variants อื่นช่วยลด space complexity นี้ได้

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python