Basic Sorting

รู้จัก Insertion Sort

Insertion Sort คืออัลกอริทึมเรียงข้อมูลที่ทำงานโดยค่อย ๆ สร้างส่วนที่เรียงแล้วจากซ้ายไปขวา — ในแต่ละรอบเราจะหยิบสมาชิกตัวถัดไปเป็น key แล้วแทรกกลับเข้าไปในตำแหน่งที่เหมาะสมภายในส่วนที่เรียงแล้ว

จุดเด่นที่สุดของ Insertion Sort คือทำงานได้ดีมากกับข้อมูลที่เกือบเรียงอยู่แล้ว — ถ้าแต่ละ key อยู่ใกล้ตำแหน่งที่ถูกต้อง จะมีการเลื่อนสมาชิกน้อยมาก ทำให้เวลาเข้าใกล้ O(n) ในสถานการณ์จริงหลายรูปแบบ

• หยิบสมาชิกปัจจุบันเป็น key — เลื่อนสมาชิกที่มากกว่า key ไปทางขวาเพื่อเปิดช่อง
• แทรก key กลับเข้าไปในตำแหน่งที่ว่าง — ส่วนที่เรียงแล้วจะขยายจากซ้ายไปขวาทีละ 1 ตัว
• เป็น stable sort — ค่าเท่ากันจะรักษาลำดับเดิมไว้ได้

แนวคิดการเรียงไพ่ในมือ — ภาพจำที่เข้าใจง่ายที่สุด

ลองนึกภาพว่าคุณถือไพ่ในมือและกำลังเรียงไพ่จากน้อยไปมาก — มือซ้ายถือไพ่ที่เรียงแล้ว มือขวาหยิบไพ่ใบใหม่ทีละใบจากกอง จากนั้นใช้มือซ้ายเลื่อนไพ่ที่มากกว่าออกไปทางขวาเพื่อเปิดช่อง แล้วเสียบไพ่ใบใหม่เข้าไปในตำแหน่งที่ถูกต้อง

Insertion Sort ทำงานเหมือนกันทุกประการ — ก่อนเริ่มรอบที่ i เราถือว่าช่วง [0..i-1] เรียงแล้ว และสมาชิกที่ตำแหน่ง i คือ "ไพ่ใบใหม่" (key) ที่ต้องนำไปแทรก หลังจบรอบ ช่วง [0..i] จะเรียงแล้ว

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

สาธิตด้วยอาเรย์ [5, 2, 4, 6, 1, 3] เรียงจากน้อยไปมาก — 3 ขั้นตอนต่อรอบ: (1) หยิบ key (2) เลื่อนค่าที่มากกว่าไปขวา (3) แทรก key กลับ

หยิบ key (สมาชิกตำแหน่งปัจจุบัน) ออกมา — เตรียมแทรกในส่วนที่เรียงแล้ว

เลื่อนสมาชิกที่มากกว่า key ไปทางขวาทีละช่องจนเจอตำแหน่งที่เหมาะสม

• **รอบ i=1 (key=2):** ส่วนที่เรียงแล้วคือ [5], key=2 → 5>2 เลื่อน 5 ไปขวา → [_,5,4,6,1,3] → แทรก 2 ที่ตำแหน่ง 0 → [2,5,4,6,1,3]
• **รอบ i=2 (key=4):** ส่วนที่เรียงแล้วคือ [2,5], key=4 → 5>4 เลื่อน 5 ไปขวา → [2,_,5,6,1,3] → 2<4 หยุด → แทรก 4 → [2,4,5,6,1,3]
• **รอบ i=3 (key=6):** ส่วนที่เรียงแล้วคือ [2,4,5], key=6 → 5<6 ไม่ต้องเลื่อน → แทรก 6 ที่เดิม → [2,4,5,6,1,3]
• **รอบ i=4 (key=1):** ส่วนที่เรียงแล้วคือ [2,4,5,6], key=1 → เลื่อน 6→5→4→2 ไปขวาทั้งหมด → [_,2,4,5,6,3] → แทรก 1 ตำแหน่ง 0 → [1,2,4,5,6,3]
• **รอบ i=5 (key=3):** ส่วนที่เรียงแล้วคือ [1,2,4,5,6], key=3 → เลื่อน 6→5→4 ไปขวา → [1,2,_,4,5,6] → 2<3 หยุด → แทรก 3 → [1,2,3,4,5,6] เรียงสมบูรณ์

แทรก key กลับในตำแหน่งที่เหมาะสม — ส่วนที่เรียงแล้วขยายขึ้น 1 ตำแหน่ง

ภาพรวม: การเปลี่ยนแปลงของอาเรย์ทีละรอบจนเรียงสมบูรณ์

Pseudocode และโค้ด JavaScript

ฟังก์ชัน insertionSort(values):
  arr = คัดลอก values

  ทำซ้ำ i จาก 1 ถึง arr.length - 1:
    key = arr[i]
    j = i - 1

    ขณะที่ j >= 0 และ arr[j] > key:
      arr[j + 1] = arr[j]   // เลื่อนค่าที่มากกว่า key ไปทางขวา 1 ช่อง
      j = j - 1             // เดินย้อนซ้ายต่อไป

    arr[j + 1] = key        // แทรก key กลับในตำแหน่งที่ถูกต้อง

  คืนค่า arr

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

  for (let i = 1; i < arr.length; i += 1) {
    const key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j -= 1;
    }

    arr[j + 1] = key;
  }

  return arr;
}

console.log(insertionSort([5, 2, 4, 6, 1, 3]));
// [1, 2, 3, 4, 5, 6]

อธิบายทีละส่วน: • `const arr = [...values]` — สร้างสำเนาอาเรย์ • `for (let i = 1; i < arr.length; i += 1)` — เริ่มที่ i=1 เพราะตำแหน่ง 0 ถือว่าเรียงแล้วตั้งแต่ต้น • `const key = arr[i]` — หยิบสมาชิกตำแหน่ง i มาเป็น key (ค่าใช้จับคู่กับไพ่ใบใหม่) • `while (j >= 0 && arr[j] > key)` — เดินย้อนซ้ายตราบใดที่ยังมีสมาชิกที่มากกว่า key • `arr[j + 1] = arr[j]` — เลื่อนสมาชิกที่มากกว่าไปทางขวา 1 ช่อง (สร้างช่องว่าง) • `arr[j + 1] = key` — หลัง loop while จบ j+1 คือตำแหน่งที่ key ควรอยู่ — แทรกกลับ

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

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

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

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

• Best Case: O(n) — ข้อมูลเรียงอยู่แล้ว key แต่ละตัวไม่ต้องเลื่อนเลย while loop ไม่ทำงาน → linear scan ครั้งเดียว
• Average Case: O(n²) — โดยเฉลี่ยแต่ละ key ต้องเลื่อนสมาชิกประมาณครึ่งหนึ่งของส่วนที่เรียงแล้ว ≈ n²/4 ครั้ง
• Worst Case: O(n²) — ข้อมูลเรียงกลับด้าน key ต้องเลื่อนไปตำแหน่ง 0 ทุกครั้ง (i ครั้งต่อรอบ) → ≈ n²/2 ครั้ง

Space Complexity = O(1) — Insertion Sort เป็น in-place algorithm ใช้ตัวแปร key และ index j เท่านั้น **ทำไม Insertion Sort ถึงทำงานดีกับข้อมูลที่เกือบเรียง?** เมื่อข้อมูลเกือบเรียง key แต่ละตัวจะอยู่ใกล้ตำแหน่งที่ถูกต้อง — while loop เลื่อนสมาชิกน้อยมากต่อรอบ ส่งผลให้เวลารวมเข้าใกล้ O(n) ในหลายสถานการณ์จริง ทำให้ Insertion Sort มักถูกเลือกใช้ในระบบที่รับข้อมูลเข้ามาทีละตัวและต้องการรักษาสถานะเรียงไว้ตลอดเวลา

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

เปรียบเทียบ Bubble Sort, Selection Sort และ Insertion Sort

ทั้งสามอัลกอริทึมเป็น O(n²) ใน Worst Case แต่มีจุดเด่น-จุดด้อยแตกต่างกัน — ตารางนี้ช่วยให้คุณเลือกใช้ได้ถูกต้องตามสถานการณ์

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

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