อัลกอริทึมการเรียงลำดับ — เปรียบเทียบ Bubble, Merge และ Quick Sort

อัลกอริทึมการเรียงลำดับคือวิธีจัดเรียงข้อมูลชุดเดิมให้อยู่ในลำดับ เช่น จากน้อยไปมาก ถ้าต้องการคำตอบสั้น ๆ ก่อน bubble sort เข้าใจง่ายแต่โดยมากช้าเกินไปสำหรับลิสต์ขนาดใหญ่ merge sort ให้ประสิทธิภาพ $O(n \log n)$ ที่สม่ำเสมอ และ quick sort มักทำงานได้เร็วในทางปฏิบัติเมื่อการแบ่งส่วนยังค่อนข้างสมดุล

คำถามที่ถูกต้องไม่ใช่ “อันไหนดีที่สุด?” แต่คือ “ดีที่สุดภายใต้เงื่อนไขแบบไหน?” Bubble sort ช่วยสอนแนวคิดการสลับตำแหน่งใกล้กัน merge sort แสดงแนวคิด divide-and-conquer ได้ชัดเจน และ quick sort แสดงให้เห็นว่าความเร็วในกรณีเฉลี่ยอาจดีมากได้ แม้จะไม่มีการรับประกันในกรณีแย่ที่สุด

อัลกอริทึมการเรียงลำดับทำอะไร

ให้ลิสต์อย่าง $[5, 1, 4, 2]$ อัลกอริทึมควรคืนค่าชุดเดิมในลำดับที่เรียงแล้ว:

$$[1, 2, 4, 5]$$

ฟังดูเหมือนง่าย แต่แต่ละอัลกอริทึมไปถึงผลลัพธ์นี้ด้วยวิธีที่ต่างกันมาก ความแตกต่างหลักคือ:

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

Bubble Sort: สลับข้อมูลข้างเคียงซ้ำ ๆ

Bubble sort จะไล่ดูข้อมูลในลิสต์และสลับสมาชิกที่อยู่ติดกันถ้าเรียงผิดลำดับ หลังจากครบหนึ่งรอบ สมาชิกที่มากที่สุดในส่วนที่ยังไม่เรียงจะ “ลอย” ไปอยู่ท้ายลิสต์

สำหรับ $[5, 1, 4, 2]$ รอบแรกจะเป็นแบบนี้:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

จากนั้นก็ทำซ้ำกับส่วนที่ยังไม่เรียงจนกว่าจะไม่ต้องสลับอีก

Bubble sort มีประโยชน์หลักในด้านการเรียนรู้ โดยทั่วไปมันมี time complexity เท่ากับ $O(n^2)$ ดังนั้นจำนวนการเปรียบเทียบจะเพิ่มขึ้นเร็วมากเมื่อขนาดลิสต์ใหญ่ขึ้น สำหรับตัวอย่างเล็ก ๆ ในห้องเรียนถือว่าใช้ได้ แต่สำหรับงานเรียงลำดับจริงจัง มักไม่ใช่ตัวเลือกที่เหมาะ

Merge Sort: แบ่ง เรียง แล้วรวม

Merge sort ใช้แนวคิด divide-and-conquer โดยจะแบ่งลิสต์ออกเป็นส่วนย่อย ๆ เรียงแต่ละส่วน แล้วค่อยรวมส่วนที่เรียงแล้วกลับเข้าด้วยกัน

สำหรับ $[5, 1, 4, 2]$ มุมมองที่ชัดเจนแบบหนึ่งคือ:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

เรียงแต่ละครึ่ง:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

จากนั้นรวมสองครึ่งที่เรียงแล้ว:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

จุดเด่นหลักของ merge sort คือความคาดเดาได้ เวลาในการทำงานของมันเป็น $O(n \log n)$ ตามการวิเคราะห์มาตรฐาน ไม่ใช่แค่ในกรณีเฉลี่ยเท่านั้น ต้นทุนหลักคือหน่วยความจำ เพราะการติดตั้งใช้งานทั่วไปกับอาร์เรย์มักต้องใช้พื้นที่เพิ่มระหว่างการรวม

Quick Sort: แบ่งรอบ Pivot

Quick sort ก็ใช้แนวคิด divide-and-conquer เช่นกัน แต่ทำในอีกแบบหนึ่ง มันเลือก pivot จัดสมาชิกที่น้อยกว่าไว้ด้านหนึ่ง และสมาชิกที่มากกว่าไว้อีกด้านหนึ่ง แล้วจึงเรียงทั้งสองด้านแบบเรียกซ้ำ

ถ้าใช้ pivot เป็น $4$ กับ $[5, 1, 4, 2]$ การแบ่งแบบหนึ่งที่เป็นไปได้คือ:

$$[1, 2] \;|\; 4 \;|\; [5]$$

ตอนนี้ส่วนซ้ายและขวามีขนาดเล็กลงมาก การเรียงจึงจบได้เร็ว

Quick sort มักเร็วในทางปฏิบัติ เพราะหลายการติดตั้งใช้งานสามารถแบ่งข้อมูลแบบ in-place และลดขนาดปัญหาได้เร็วเมื่อ pivot แบ่งลิสต์ได้ค่อนข้างดี แต่เงื่อนไขนี้สำคัญมาก ถ้าการเลือก pivot แย่ซ้ำ ๆ เช่น ได้ด้านหนึ่งเล็กมากและอีกด้านเกือบเต็มอยู่เรื่อย ๆ กรณีแย่ที่สุดจะกลายเป็น $O(n^2)$

Bubble Sort vs Merge Sort vs Quick Sort

อัลกอริทึม	แนวคิดหลัก	เวลาทั่วไป	เวลาในกรณีแย่ที่สุด	หน่วยความจำเพิ่มเติม
Bubble sort	สลับสมาชิกที่อยู่ติดกันซ้ำ ๆ	$O(n^2)$	$O(n^2)$	ต่ำ
Merge sort	แบ่ง เรียงแต่ละครึ่ง แล้วรวม	$O(n \log n)$	$O(n \log n)$	สูงกว่าในการติดตั้งใช้งานกับอาร์เรย์ทั่วไป
Quick sort	แบ่งรอบ pivot	มักเป็น $O(n \log n)$	$O(n^2)$	มักน้อยกว่า merge sort

ถ้าจะสรุปแบบใช้งานได้จริงหนึ่งข้อ ก็คือ bubble sort เป็นอัลกอริทึมเพื่อการสอน merge sort เป็นตัวเลือกที่นิ่งและคาดเดาได้ และ quick sort มักเป็นตัวเลือกด้านความเร็วในทางปฏิบัติเมื่อการติดตั้งใช้งานจัดการ pivot ได้ดี

ตัวอย่างเดียวกันแบบลงมือดู

ใช้ลิสต์เดิม:

$$[5, 1, 4, 2]$$

Bubble sort จะคอยแก้ความผิดพลาดเฉพาะจุดที่อยู่ใกล้กัน มันไม่ได้ “มองเห็น” โครงสร้างทั้งหมด จึงอาจต้องผ่านหลายรอบ

Merge sort จะแยกปัญหาออกเป็นชิ้นเล็ก ๆ ที่เรียงได้ก่อน แล้วค่อยรวมกลับเข้าด้วยกัน โครงสร้างนี้เองที่ทำให้ประสิทธิภาพของมันยังคงสม่ำเสมอเมื่อขนาดลิสต์ใหญ่ขึ้น

Quick sort พยายามสร้างการแบ่งที่ดีตั้งแต่ต้น ถ้าการแบ่งสมดุลพอ งานที่เหลือจะหดลงอย่างรวดเร็ว

นี่จึงเป็นเหตุผลที่นักเรียนมักจำค่าความซับซ้อนได้ดีขึ้นหลังจากเห็นลิสต์เดียวกันเคลื่อนผ่านแต่ละวิธี ตัวเลขเหล่านั้นไม่ใช่แค่ป้ายกำกับลอย ๆ แต่มันสะท้อนว่าอัลกอริทึมลดความไม่เป็นระเบียบอย่างไร

ข้อผิดพลาดที่พบบ่อยเมื่อเปรียบเทียบอัลกอริทึมการเรียงลำดับ

คิดว่า Quick Sort เร็วกว่าเสมอ

Quick sort มักเร็วในทางปฏิบัติ แต่ไม่ได้รับประกันว่าจะเร็วที่สุดในทุกกรณี การเลือก pivot ที่ไม่ดีอาจทำให้ประสิทธิภาพแย่ลงมาก

มองว่าอัลกอริทึม $O(n \log n)$ เหมือนกันหมด

Merge sort และ quick sort อาจมีอัตราการเติบโตเฉลี่ยแบบเดียวกัน แต่ไม่ได้หมายความว่าจะเหมือนกันในเรื่องการใช้หน่วยความจำ การรับประกันกรณีแย่ที่สุด หรือรายละเอียดการติดตั้งใช้งาน

ใช้ Bubble Sort เพราะเขียนโค้ดง่าย

การเขียนง่ายไม่ได้แปลว่าเหมาะสม สำหรับเดโมเล็ก ๆ bubble sort ใช้ได้ แต่กับข้อมูลจริงที่ใหญ่ขึ้น มันมักทำงานเกินความจำเป็น

ลืมสมมติฐานของข้อมูลนำเข้า

การเปรียบเทียบเหล่านี้มักสมมติว่าเป็นการเรียงลำดับแบบอาศัยการเปรียบเทียบบนข้อมูลทั่วไป ถ้าข้อมูลมีโครงสร้างพิเศษ การเรียงแบบไม่ใช้การเปรียบเทียบ เช่น counting sort อาจเปลี่ยนคำตอบไปโดยสิ้นเชิง

อัลกอริทึมการเรียงลำดับแต่ละแบบใช้เมื่อไร

Bubble sort ส่วนใหญ่ใช้เพื่อการสอน การไล่ดูขั้นตอน และตัวอย่างขนาดเล็กมากที่ความชัดเจนสำคัญกว่าประสิทธิภาพ

Merge sort ใช้เมื่อพฤติกรรม $O(n \log n)$ ที่สม่ำเสมอมีความสำคัญ และยอมรับการใช้หน่วยความจำเพิ่มเติมได้ นอกจากนี้ยังเหมาะตามธรรมชาติกับ linked list และกับสถานการณ์ที่การเรียงลำดับแบบ stable มีความสำคัญ ทั้งนี้ขึ้นอยู่กับการติดตั้งใช้งาน

Quick sort ใช้เมื่อความเร็วในทางปฏิบัติสำคัญ และการติดตั้งใช้งานมีกลยุทธ์เลือก pivot ที่ดีหรือมีตัวป้องกันสำรอง หลายกลยุทธ์การเรียงลำดับใน standard library ใช้แนวคิดของ quick sort ร่วมกับมาตรการป้องกัน แทนที่จะใช้เวอร์ชันพื้นฐานแบบในตำราโดยตรง

วิธีจำความต่างแบบเร็ว ๆ

จำผ่านลักษณะการเคลื่อนที่:

• bubble sort แก้คู่ข้างเคียง
• merge sort สร้างครึ่งที่เรียงแล้ว
• quick sort แบ่งรอบ pivot

ภาพในหัวแบบนี้มีประโยชน์กว่าการท่องจำชื่อสามชื่อกับสูตรสามสูตร

ลองทำเวอร์ชันของคุณเอง

นำลิสต์ $[7, 3, 6, 1]$ มาลองไล่ดูหนึ่งรอบของ bubble sort หนึ่งรอบของการแบ่งและรวมใน merge sort และหนึ่งครั้งของการแบ่งด้วย pivot ใน quick sort ถ้าคุณอธิบายได้ว่าทำไมลิสต์จึงเปลี่ยนไปต่างกันในแต่ละกรณี แปลว่าคุณเข้าใจแนวคิดนี้แล้ว