merge-sort-and-quick-sort

การทำความเข้าใจเกี่ยวกับ Merge Sort และ Quick Sort

ทั้ง Merge Sort และ Quick Sort เป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพสูง ซึ่งใช้หลักการของ Divide and Conquer (แบ่งและพิชิต) ในการจัดเรียงข้อมูลทั้งสองอัลกอริธึมนี้มีประสิทธิภาพที่ดีกว่าอัลกอริธึมการเรียงลำดับแบบ Bubble Sort หรือ Selection Sort ที่มีความซับซ้อน O(n²) แต่ทั้งสองมีลักษณะการทำงานที่แตกต่างกัน

---

1. Merge Sort (การเรียงลำดับแบบผสาน)

Merge Sort เป็นอัลกอริธึมแบบ Divide and Conquer ที่แบ่งข้อมูลออกเป็นสองส่วนย่อยๆ และทำการเรียงลำดับในแต่ละส่วนก่อนจะนำทั้งสองส่วนมาผสานกันอย่างมีระเบียบ

ขั้นตอนของ Merge Sort:

1. แบ่งลิสต์ออกเป็นสองส่วนเท่าๆ กันจนกระทั่งลิสต์มีขนาด 1 (หรือเป็นลิสต์ว่าง)
2. ทำการรวมลิสต์ที่แบ่งออกมาแล้ว โดยการนำค่าจากลิสต์ที่แบ่งมาเปรียบเทียบกันและนำมาวางเรียงลำดับ
3. ทำซ้ำขั้นตอนการรวมจนกว่าจะได้ลิสต์ที่เรียงลำดับสมบูรณ์

ตัวอย่างการทำงานของ Merge Sort:

สมมุติว่ามีลิสต์ [38, 27, 43, 3, 9, 82, 10] ซึ่งเราต้องการให้เรียงลำดับ

1. แบ่งลิสต์:
   • [38, 27, 43, 3] และ [9, 82, 10]
2. แบ่งย่อยลงไปอีก:
   • [38, 27], [43, 3], [9, 82], [10]
3. เรียงลำดับแต่ละส่วน:
   • [27, 38], [3, 43], [9, 82], [10]
4. รวม:
   • [3, 27, 38, 43] และ [9, 10, 82]
5. รวมสุดท้าย: [3, 9, 10, 27, 38, 43, 82]

ตัวอย่างโค้ด Merge Sort (Python):

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))

ผลลัพธ์:

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

ข้อดีของ Merge Sort:

• ประสิทธิภาพสูง (O(n log n)) สำหรับข้อมูลที่มีขนาดใหญ่
• ดีสำหรับการจัดการกับข้อมูลขนาดใหญ่หรือข้อมูลที่ไม่ได้อยู่ในหน่วยความจำทั้งหมด
• ไม่ขึ้นอยู่กับการเรียงลำดับก่อนหน้าในข้อมูล (สามารถทำงานได้ดีแม้ข้อมูลจะไม่เรียงลำดับ)

ข้อเสียของ Merge Sort:

• ต้องใช้หน่วยความจำเพิ่มเติม (O(n)) สำหรับการจัดเก็บข้อมูลระหว่างขั้นตอนการรวม
• ช้ากว่าในกรณีที่ข้อมูลมีขนาดเล็ก

---

2. Quick Sort (การเรียงลำดับแบบเร็ว)

Quick Sort ก็เป็นอัลกอริธึมแบบ Divide and Conquer ที่ใช้หลักการการเลือก pivot (จุดกึ่งกลาง) และจัดลำดับค่าภายในลิสต์ด้วยการเปรียบเทียบค่ากับ pivot ซึ่งการแบ่งลิสต์จะเกิดขึ้นจนกว่าลิสต์ทั้งหมดจะถูกจัดเรียง

ขั้นตอนของ Quick Sort:

1. เลือก pivot จากข้อมูลในลิสต์ (สามารถเลือก pivot ได้หลายวิธี เช่น เลือกค่ากลาง, ค่าต้น, หรือค่าปลาย)
2. แบ่งข้อมูลออกเป็นสองส่วน: ข้อมูลที่น้อยกว่าหรือเท่ากับ pivot ไปทางซ้าย, ข้อมูลที่มากกว่าหรือเท่ากับ pivot ไปทางขวา
3. เรียกฟังก์ชัน Quick Sort ซ้ำในทั้งสองส่วนย่อย
4. ทำขั้นตอนนี้จนกว่าลิสต์ทั้งหมดจะเรียงลำดับ

ตัวอย่างการทำงานของ Quick Sort:

สมมุติว่ามีลิสต์ [38, 27, 43, 3, 9, 82, 10] ซึ่งเราต้องการให้เรียงลำดับ

1. เลือก pivot เป็น 43:
   • สร้างสองกลุ่ม: [38, 27, 3, 9, 10] และ [82]
2. เรียงลำดับกลุ่มซ้าย: [3, 9, 10, 27, 38]
3. รวมกลุ่ม: [3, 9, 10, 27, 38, 43, 82]

ตัวอย่างโค้ด Quick Sort (Python):

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))

ผลลัพธ์:

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

ข้อดีของ Quick Sort:

• ประสิทธิภาพดีมาก (O(n log n)) สำหรับข้อมูลขนาดใหญ่
• ใช้หน่วยความจำต่ำกว่าการใช้ Merge Sort เพราะไม่ต้องใช้พื้นที่เพิ่มเติมมากนัก
• มีการทำงานที่รวดเร็วและมีประสิทธิภาพสำหรับข้อมูลที่มีขนาดใหญ่และไม่ได้เรียงลำดับมาก่อน

ข้อเสียของ Quick Sort:

• หากการเลือก pivot ไม่ดี (เช่น เลือกค่าที่สุดโต่ง) อาจทำให้เวลาในการประมวลผลเพิ่มขึ้นถึง O(n²)
• ใช้เวลาในการทำงานสูงในกรณีที่ข้อมูลมีลักษณะเฉพาะ (เช่น ข้อมูลซ้ำกันหรือข้อมูลเรียงลำดับแล้ว)

---

เปรียบเทียบระหว่าง Merge Sort และ Quick Sort

คุณสมบัติ	Merge Sort	Quick Sort
ความซับซ้อนของเวลา	O(n log n)	O(n log n) แต่ในกรณีแย่ O(n²)
การใช้หน่วยความจำ	ใช้หน่วยความจำเพิ่มเติม O(n)	ใช้หน่วยความจำต่ำกว่า (in-place sort)
การทำงานกับข้อมูลที่เรียงลำดับแล้ว	ดีเยี่ยม	อาจประสิทธิภาพต่ำในกรณีข้อมูลเรียงลำดับแล้ว
ความเร็วในกรณีทั่วไป	ช้ากว่า Quick Sort ในหลายกรณี	เร็วกว่าหากการเลือก pivot ดี
ความซับซ้อนในการนำไปใช้	ง่ายและเหมาะสำหรับข้อมูลขนาดใหญ่	ยากกว่าเล็กน้อย แต่เร็วกว่าหากเลือก pivot ดี

---

สรุป:

• Merge Sort: เป็นอัลกอริธึมที่เชื่อถือได้และมีประสิทธิภาพสำหรับข้อมูลขนาดใหญ่ แต่ต้องการหน่วยความจำเพิ่มเติม
• Quick Sort: เป็นอัลกอริธึมที่มีประสิทธิภาพสูงและเร็วกว่าในหลายกรณี แต่ขึ้นอยู่กับการเลือก pivot หากเลือกไม่ดีอาจทำให้เวลาในการทำงานแย่ลง