Selection Sort แบบละเอียดสำหรับผู้เริ่มต้น
จุดสำคัญของบทนี้คือเข้าใจให้ชัดว่าในทุก ๆ รอบ เราจะเลือกค่าน้อยที่สุดจาก ส่วนที่ยังไม่เรียง แล้วนำมาไว้ด้านหน้าเพื่อขยายส่วนที่เรียงแล้วทีละตำแหน่ง
1. Selection Sort คืออะไร
Selection Sort คืออัลกอริทึมเรียงข้อมูลที่ทำงานแบบ “เลือกก่อนแล้วค่อยสลับ” โดยในแต่ละรอบจะค้นหาค่าที่น้อยที่สุดจากช่วงที่ยังไม่เรียง และนำค่านั้นมาไว้ตำแหน่งหน้าสุดของช่วงนั้น
เมื่อจบรอบแรก ตำแหน่งแรกจะถูกต้องแน่นอน จบรอบที่สอง ตำแหน่งที่สองจะถูกต้องแน่นอน ทำซ้ำไปเรื่อย ๆ จนเรียงครบทั้งอาเรย์
2. หลักการทำงาน
แต่ละรอบมี 3 ขั้นตอน: (1) กำหนดตำแหน่งเริ่มต้นของช่วงที่ยังไม่เรียง (2) ไล่หาค่าน้อยสุดในช่วงนั้น (3) สลับค่าน้อยสุดกลับมาไว้ตำแหน่งเริ่มต้น
เพราะเราเลือกค่าน้อยสุดได้ถูกต้องในแต่ละรอบ ส่วนที่เรียงแล้วจึงขยายจากซ้ายไปขวาอย่างเป็นระบบ
3. แนวคิด “แบ่งส่วนที่เรียงแล้ว” กับ “ส่วนที่ยังไม่เรียง”
ในมุมมองของ Selection Sort อาเรย์ถูกแบ่งเป็น 2 ส่วนเสมอ: ด้านซ้ายคือส่วนที่เรียงแล้ว และด้านขวาคือส่วนที่ยังไม่เรียง
4. ตัวอย่าง array เช่น [29, 10, 14, 37, 13]
เราจะเรียงข้อมูลจากน้อยไปมาก โดยเริ่มจากอาเรย์:[29, 10, 14, 37, 13]
5. อธิบายรอบที่ 1 ว่าหาค่าน้อยสุดจากช่วงที่ยังไม่เรียงอย่างไร
รอบที่ 1: ช่วงที่ยังไม่เรียงคือทั้งอาเรย์ เราเริ่มถือว่า 29 เป็นค่าน้อยสุดชั่วคราว แล้วไล่เทียบกับ 10, 14, 37, 13 จะพบว่าค่าน้อยสุดจริงคือ 10
6. อธิบายการสลับมาไว้ด้านหน้า
เมื่อได้ค่าน้อยสุด (10) แล้ว เราจะสลับกับสมาชิกตำแหน่งหน้า (29) ทำให้ค่าที่ถูกต้องสำหรับตำแหน่งแรกถูกล็อกทันที
7. ทำต่อรอบที่ 2, 3, ... จนเสร็จ
หลังรอบที่ 1: [10, 29, 14, 37, 13] ตอนนี้ตำแหน่งที่ 0 เรียงแล้ว
รอบที่ 2: หา minimum ในช่วง [29, 14, 37, 13] ได้ 13 แล้วสลับกับ 29 ผลลัพธ์เป็น [10, 13, 14, 37, 29]
รอบที่ 3: หา minimum ในช่วง [14, 37, 29] ได้ 14 อยู่ตำแหน่งเดิม ไม่ต้องสลับ
รอบที่ 4: หา minimum ในช่วง [37, 29] ได้ 29 แล้วสลับกับ 37 จบเป็น [10, 13, 14, 29, 37]
8. Pseudocode
โครงแนวคิดก่อนแปลงเป็นโค้ดจริง
9. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย
ค้นหา minimum ในแต่ละรอบ แล้วสลับมาไว้ด้านหน้า
ลูปนอกกำหนดตำแหน่งที่เรากำลังจะ “ล็อกค่าให้ถูกต้อง” ส่วนลูปในใช้ไล่หา index ของค่าน้อยสุดจากช่วงที่ยังไม่เรียง เมื่อหาเจอแล้วค่อยสลับทีเดียว
10. Best / Average / Worst Time Complexity
Best: O(n²)
ถึงแม้ข้อมูลเรียงอยู่แล้ว ก็ยังต้องไล่หา minimum ในทุกช่วง
Average: O(n²)
โดยทั่วไปยังต้องเปรียบเทียบเป็นลูปซ้อนใกล้เคียง n(n-1)/2 ครั้ง
Worst: O(n²)
กรณีแย่ที่สุดก็ยังไม่เกินกรอบเดียวกัน เพราะจำนวนการเทียบเท่าเดิม
11. Space Complexity
ถ้าเรียงแบบ in-place จะใช้หน่วยความจำเพิ่มเพียงตัวแปรชั่วคราวไม่กี่ตัว ดังนั้น Space Complexity เป็น O(1)
12. ข้อดี
เข้าใจง่าย เหมาะกับการเริ่มต้นเรียนการเรียงข้อมูล
จำนวนครั้งในการสลับค่าค่อนข้างน้อย (สูงสุดประมาณ n-1 ครั้ง)
โค้ดกระชับและเป็นพื้นฐานที่ดีสำหรับการฝึก loop + index
13. ข้อเสีย
ประสิทธิภาพเวลา O(n²) จึงช้ากับข้อมูลขนาดใหญ่
ไม่ใช่อัลกอริทึมแบบ stable ในรูปแบบพื้นฐาน
แม้ข้อมูลเกือบเรียงแล้วก็ยังต้องวนหา minimum แทบทุกรอบ
14. เปรียบเทียบสั้น ๆ กับ Bubble Sort
Bubble Sort จะเทียบสมาชิกที่ติดกันและสลับบ่อยมากในแต่ละ pass ส่วน Selection Sort จะหา minimum แล้วสลับทีเดียวต่อรอบ จึงมักมีจำนวนการสลับน้อยกว่า Bubble Sort
15. เปรียบเทียบสั้น ๆ กับ Insertion Sort
Insertion Sort ทำงานแบบหยิบสมาชิกใหม่มาแทรกในส่วนที่เรียงแล้ว และมักเร็วกว่า Selection Sort เมื่อข้อมูลเกือบเรียงอยู่แล้ว แต่ Selection Sort มีแนวคิดเลือก minimum ที่ตรงไปตรงมาและท่องจำง่าย
16. สรุปท้ายบท
จำสั้น ๆ: “แต่ละรอบเลือกค่าน้อยสุดจากส่วนที่ยังไม่เรียง แล้วสลับมาไว้ด้านหน้า” เมื่อทำซ้ำครบทุกรอบ อาเรย์จะเรียงจากน้อยไปมาก
Selection Sort จึงเหมาะสำหรับเรียนหลักคิดเรื่อง index, loop ซ้อน และการจัดช่วงข้อมูล ก่อนต่อยอดไปยังอัลกอริทึมที่เร็วกว่าในงานจริง
17. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย (ใช้ playground)
ข้อ 1: เขียนฟังก์ชัน selectionSort(values)
แนวเฉลยย่อ: ใช้ลูปนอกกำหนด i, ลูปในหา minIndex แล้วสลับ arr[i] กับ arr[minIndex]
ข้อ 2: เขียน selectionSortPass(values, startIndex) ให้ทำเพียง 1 รอบ
แนวเฉลยย่อ: หา minimum ตั้งแต่ startIndex ถึงท้ายอาเรย์ แล้วสลับแค่ครั้งเดียว
ข้อ 3: เขียน findMinIndex(values, startIndex)
แนวเฉลยย่อ: เก็บ minIndex เริ่มต้นที่ startIndex แล้วไล่เปรียบเทียบเพื่อคืน index ของค่าน้อยสุด
ฝึกลงมือจริงพร้อม runtime checks ได้ใน Selection Sort Lab ซึ่งจะแยกเป็น 3 โจทย์ตามแบบฝึกด้านบน