Basic Sorting

รู้จัก Selection Sort

Selection Sort คืออัลกอริทึมเรียงข้อมูลที่ใช้แนวคิด "เลือกก่อนแล้วค่อยสลับ" — ในแต่ละรอบเราจะค้นหาค่าที่น้อยที่สุด (หรือมากที่สุด) ในช่วงที่ยังไม่เรียง แล้วสลับค่านั้นไปไว้ตำแหน่งหน้าสุดของช่วง

ข้อแตกต่างที่สำคัญจาก Bubble Sort: Bubble Sort จะสลับสมาชิกที่ติดกันบ่อยครั้งในแต่ละ pass แต่ Selection Sort จะหา minimum ให้เจอก่อน แล้วสลับเพียงครั้งเดียวต่อรอบ — ทำให้จำนวนครั้งในการสลับน้อยกว่า Bubble Sort มาก

• แต่ละรอบค้นหาค่าน้อยสุดจากส่วนที่ยังไม่เรียง
• สลับค่าน้อยสุดนั้นมาไว้ตำแหน่งหน้าสุดของช่วง — สลับแค่ครั้งเดียวต่อรอบ
• ส่วนที่เรียงแล้วขยายจากซ้ายไปขวาทีละตำแหน่งในแต่ละรอบ

แนวคิด "ส่วนที่เรียงแล้ว" กับ "ส่วนที่ยังไม่เรียง"

ในมุมมองของ Selection Sort อาเรย์จะถูกแบ่งเป็น 2 ส่วนเสมอ: ด้านซ้ายคือส่วนที่เรียงแล้ว (sorted partition) และด้านขวาคือส่วนที่ยังไม่เรียง (unsorted partition)

เมื่อเริ่มต้น ส่วนที่เรียงแล้วจะว่างเปล่า ทุกครั้งที่เราหา minimum จากฝั่งขวาแล้วสลับมาไว้หน้าสุด ส่วนที่เรียงแล้วจะขยายออกไป 1 ตำแหน่ง และส่วนที่ยังไม่เรียงจะหดลง 1 ตำแหน่ง — ทำซ้ำจนส่วนที่ยังไม่เรียงว่างเปล่า

ด้านซ้าย (สีเข้ม) = ส่วนที่เรียงแล้ว — ด้านขวา (สีอ่อน) = ส่วนที่ยังไม่เรียง

ขั้นตอนการทำงานทีละขั้น

เราจะสาธิตด้วยอาเรย์ [29, 10, 14, 37, 13] โดยเรียงจากน้อยไปมาก มาดูกันว่า Selection Sort เลือกและสลับอย่างไรในแต่ละรอบ

แต่ละรอบค้นหาค่าน้อยสุดจากส่วนที่ยังไม่เรียง (สีอ่อน) แล้วไฮไลต์ไว้

• **รอบที่ 1:** ค้นหาค่าน้อยสุดใน [29,10,14,37,13] → พบ 10 คือค่าน้อยสุด → สลับ 10 กับ 29 → ได้ [10, 29, 14, 37, 13] ตอนนี้ตำแหน่ง 0 เรียงแล้ว
• **รอบที่ 2:** ค้นหาค่าน้อยสุดในส่วนที่ยังไม่เรียง [29,14,37,13] → พบ 13 คือค่าน้อยสุด → สลับ 13 กับ 29 → ได้ [10, 13, 14, 37, 29] ตำแหน่ง 0-1 เรียงแล้ว
• **รอบที่ 3:** ค้นหาใน [14,37,29] → พบ 14 อยู่ตำแหน่งเดิม → ไม่ต้องสลับ → [10, 13, 14, 37, 29] ตำแหน่ง 0-2 เรียงแล้ว
• **รอบที่ 4:** ค้นหาใน [37,29] → พบ 29 คือค่าน้อยสุด → สลับ 29 กับ 37 → ได้ [10, 13, 14, 29, 37] เรียงสมบูรณ์

ค่าน้อยสุดที่ถูกเลือก (สีเขียว) จะถูกสลับมาไว้ตำแหน่งหน้าสุดของช่วงที่ยังไม่เรียง

สังเกตว่า Selection Sort สลับเพียง 3 ครั้งสำหรับอาเรย์ 5 ตัว (สูงสุด n-1 = 4 ครั้ง) — น้อยกว่า Bubble Sort ที่ต้องสลับหลายสิบครั้งในกรณีเดียวกัน

Pseudocode และโค้ด JavaScript

ฟังก์ชัน selectionSort(values):
  arr = คัดลอก values
  n = จำนวนสมาชิกของ arr

  ทำซ้ำ i จาก 0 ถึง n - 2:
    minIndex = i

    ทำซ้ำ j จาก i + 1 ถึง n - 1:
      ถ้า arr[j] < arr[minIndex]:
        minIndex = j

    ถ้า minIndex ไม่เท่ากับ i:
      สลับ arr[i] กับ arr[minIndex]

  คืนค่า arr

function selectionSort(values) {
  const arr = [...values];

  for (let i = 0; i < arr.length - 1; i += 1) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j += 1) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr;
}

console.log(selectionSort([29, 10, 14, 37, 13]));
// [10, 13, 14, 29, 37]

อธิบายทีละส่วน: • `const arr = [...values]` — สร้างสำเนาอาเรย์ • `for (let i = 0; i < arr.length - 1; i += 1)` — ลูปนอก: i คือตำแหน่งที่เรากำลังจะล็อกค่าให้ถูกต้อง (ขยาย sorted partition) • `let minIndex = i` — ตั้งสมมติฐานว่าตำแหน่ง i มีค่าน้อยสุดในส่วนที่ยังไม่เรียง • `for (let j = i + 1; j < arr.length; j += 1)` — ลูปใน: ไล่หาค่าที่น้อยกว่า minIndex จริง • `if (minIndex !== i)` — ถ้าค่าน้อยสุดไม่ได้อยู่ที่ i ตั้งแต่แรก จึงสลับ — ไม่เช่นนั้นไม่ต้องทำอะไร

ดูโค้ดทำงานทีละขั้นด้วย Code Trace

ทดลองเขียนด้วยตัวเอง

ได้เวลาลงมือเขียน Selection Sort — เริ่มจากการเขียนฟังก์ชันหา index ของค่าน้อยสุดก่อน แล้วค่อยประกอบเป็น Selection Sort ที่สมบูรณ์

วิเคราะห์ประสิทธิภาพ (Time & Space Complexity)

• Best Case: O(n²) — ถึงแม้ข้อมูลจะเรียงอยู่แล้ว ก็ยังต้องไล่หา minimum ในทุกช่วง เพราะ Selection Sort ไม่มีทางรู้ว่าข้อมูลเรียงแล้วจนกว่าจะตรวจครบทุกตัว
• Average Case: O(n²) — จำนวนการเปรียบเทียบ = n(n-1)/2 ≈ n²/2 ครั้งในทุกกรณี
• Worst Case: O(n²) — กรณีแย่ที่สุดก็ยังอยู่ในกรอบเดียวกัน เพราะจำนวนการเปรียบเทียบเท่าเดิมไม่ว่าข้อมูลจะเป็นอย่างไร

Space Complexity = O(1) — Selection Sort เป็น in-place algorithm ใช้ตัวแปร i, j, minIndex, temp เท่านั้น ไม่ต้องสร้างโครงสร้างข้อมูลใหม่ หมายเหตุ: ต่างจาก Bubble Sort ที่ Best Case อาจเป็น O(n) ได้เมื่อใช้ optimized version — Selection Sort ไม่มี early exit เพราะต้องตรวจข้อมูลทั้งหมดเพื่อหา minimum เสมอ

ข้อดี ข้อเสีย และกรณีใช้งาน

เปรียบเทียบกับ Bubble Sort

กฎสำคัญที่ต้องจำ

ทบทวนความเข้าใจ