การค้นหาและการเรียงลำดับบทที่ 19Insertion Sort

Insertion Sort แบบละเอียดและเป็นระบบสำหรับผู้เริ่มต้น

แกนสำคัญของบทนี้คือเข้าใจว่าเราจะหยิบข้อมูลทีละตัว (key) แล้วนำไปแทรกในตำแหน่งที่ถูกต้อง ของส่วนที่เรียงแล้ว ซึ่งคล้ายกับการเรียงไพ่ในมือทีละใบ

1. Insertion Sort คืออะไร

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

จุดเด่นคือโครงคิดเข้าใจง่ายมาก และมักทำงานได้ดีเมื่อข้อมูลเดิมเกือบเรียงอยู่แล้ว

2. เปรียบเทียบกับการเรียงไพ่ในมือ

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

Insertion Sort ทำงานเหมือนกันทุกประการ ต่างแค่ว่าเปลี่ยนจากไพ่เป็นสมาชิกใน array

3. หลักการแบ่งส่วนที่เรียงแล้วกับข้อมูลที่ยังไม่เรียง

ก่อนเริ่มรอบที่ i เราถือว่าช่วงซ้าย [0..i-1] เรียงแล้ว และสมาชิกที่ตำแหน่ง i คือ key ที่ต้องนำไปแทรก หลังจบรอบ ช่วง [0..i] จะเรียงแล้ว

4. ตัวอย่าง array เช่น [5, 2, 4, 6, 1, 3]

เราจะเรียงจากน้อยไปมาก โดยใช้อาเรย์ตัวอย่าง:[5, 2, 4, 6, 1, 3]

5. อธิบายการหยิบ key ออกมาแล้วเลื่อนสมาชิกที่มากกว่าไปทางขวา

สมมติรอบแรก key = 2 (ตำแหน่ง i=1) เราจะเปรียบเทียบย้อนซ้าย หากเจอสมาชิกที่มากกว่า key (เช่น 5) ก็เลื่อนไปขวา 1 ช่องทันที เพื่อเตรียมช่องว่างสำหรับแทรก key

ภาพแสดงการหยิบ key ออกจากอาเรย์ใน Insertion Sort

ภาพแสดงการเลื่อนสมาชิกที่มากกว่า key ไปทางขวาใน Insertion Sort

6. อธิบายการแทรก key กลับเข้าไปในตำแหน่งที่ถูกต้อง

เมื่อเลื่อนค่าที่มากกว่า key ออกไปแล้ว ช่องว่างที่ตำแหน่ง j + 1จะเป็นตำแหน่งที่เหมาะสมสำหรับ key เราจึงใส่ key กลับเข้าไปตรงนั้น

ภาพแสดงการแทรก key กลับเข้าไปในตำแหน่งที่ถูกต้องของ Insertion Sort

7. อธิบายทีละรอบอย่างละเอียด

สรุปลำดับผลลัพธ์แต่ละรอบของ [5, 2, 4, 6, 1, 3]: รอบ i=1 ได้ [2, 5, 4, 6, 1, 3], รอบ i=2 ได้ [2, 4, 5, 6, 1, 3], รอบ i=3 ยังเป็น [2, 4, 5, 6, 1, 3], รอบ i=4 ได้ [1, 2, 4, 5, 6, 3], รอบ i=5 ได้ [1, 2, 3, 4, 5, 6]

ภาพ step-by-step แสดงการเปลี่ยนแปลงของอาเรย์แต่ละรอบใน Insertion Sort

8. Pseudocode

Pseudocode: Insertion Sortbash

โครงความคิดก่อนลงมือเขียนโค้ดจริง

ฟังก์ชัน 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 ไปทางขวา
      j = j - 1

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

  คืนค่า arr

9. ตัวอย่างโค้ด JavaScript พร้อมอธิบายทีละส่วน

JavaScript: Insertion SortJS

หยิบ key, เลื่อนค่าที่มากกว่า, แล้วแทรกกลับ

function insertionSort(values) {
  const arr = [...values]; // ไม่แก้ข้อมูลต้นฉบับโดยตรง

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

    // เลื่อนสมาชิกที่มากกว่า key ไปทางขวา
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j -= 1;
    }

    // แทรก key กลับในตำแหน่งที่เหมาะสม
    arr[j + 1] = key;
  }

  return arr;
}

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

ลูป for วิ่งจากซ้ายไปขวาเพื่อหยิบ key ทีละตัว, ลูป while ใช้เลื่อนสมาชิกที่มากกว่า key ไปทางขวา, แล้วปิดท้ายด้วยการแทรก key ที่ตำแหน่ง j + 1

10. Best / Average / Worst Time Complexity

Best: O(n)

เมื่อข้อมูลเรียงอยู่แล้ว ลูป while แทบไม่เลื่อนเลย

Average: O(n²)

โดยเฉลี่ยแต่ละ key ต้องเลื่อนผ่านสมาชิกหลายตัว

Worst: O(n²)

กรณีเรียงกลับด้าน key จะต้องเลื่อนไปเกือบสุดทุกครั้ง

ทำไมมักทำงานดีบนข้อมูลที่เกือบเรียงอยู่แล้ว

เมื่อข้อมูลเกือบเรียง key แต่ละตัวจะขยับน้อยมาก ลูป while จึงทำงานสั้นลงมาก ส่งผลให้เวลารวมเข้าใกล้ O(n) ในหลายสถานการณ์จริง

11. Space Complexity

Insertion Sort แบบ in-place ใช้พื้นที่เพิ่มเพียงตัวแปร key และตัวชี้ index จึงมี Space Complexity เท่ากับ O(1)

12. ข้อดี

แนวคิดตรงไปตรงมาและเชื่อมโยงกับการเรียงไพ่ได้ง่าย

เป็นอัลกอริทึมแบบ stable (ค่าเท่ากันรักษาลำดับเดิมได้)

ทำงานดีบนข้อมูลขนาดเล็กหรือข้อมูลที่เกือบเรียงแล้ว

13. ข้อเสีย

เวลาเฉลี่ยและกรณีแย่ที่สุดเป็น O(n²) จึงไม่เหมาะกับข้อมูลขนาดใหญ่

เมื่อข้อมูลสลับตำแหน่งมาก จะมีการเลื่อนสมาชิกจำนวนมาก

ประสิทธิภาพโดยรวมแพ้อัลกอริทึมระดับ O(n log n) ในงานข้อมูลใหญ่

14. เหมาะกับกรณีไหน

เหมาะกับชุดข้อมูลขนาดเล็ก, ข้อมูลที่เกือบเรียงแล้ว, และงานที่ข้อมูลเข้ามาทีละตัว ซึ่งสามารถแทรกเข้าโครงสร้างที่เรียงอยู่แล้วได้ทันทีโดยไม่ต้องเรียงใหม่ทั้งหมด

15. เปรียบเทียบสั้น ๆ กับ Bubble Sort และ Selection Sort

เทียบกับ Bubble Sort

Bubble Sort เน้นสลับคู่ที่ติดกันหลายครั้ง ส่วน Insertion Sort เน้น “เลื่อนแล้วแทรก” จึงมักทำงานดีกว่าเมื่อข้อมูลเกือบเรียง

เทียบกับ Selection Sort

Selection Sort ต้องสแกนหา minimum ในทุกช่วงเสมอ ขณะที่ Insertion Sort สามารถจบเร็วในแต่ละรอบได้เมื่อ key อยู่ใกล้ตำแหน่งที่ถูกต้อง

16. สรุปท้ายบท

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

ถ้าเข้าใจภาพ “เรียงไพ่ในมือ” คุณจะเข้าใจ Insertion Sort ได้ไวมาก และสามารถต่อยอดไปอัลกอริทึมอื่นได้ง่ายขึ้น

17. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

ข้อ 1: เขียนฟังก์ชัน insertionSort(values) ให้เรียงจากน้อยไปมาก

แนวเฉลยย่อ: ใช้ลูป i ตั้งแต่ 1, เก็บ key, ใช้ while เลื่อนสมาชิกที่มากกว่า key, แล้วใส่ key ที่ตำแหน่ง j+1

ข้อ 2: ทำ Insertion Sort เพียง 1 รอบที่ i=4 กับ [2, 4, 5, 6, 1, 3]

แนวเฉลยย่อ: key = 1 เลื่อน 6,5,4,2 ไปขวา แล้วแทรก 1 ด้านหน้า ได้ [1, 2, 4, 5, 6, 3]

ข้อ 3: อธิบายว่าทำไม Insertion Sort ถึงเร็วขึ้นเมื่อข้อมูลเกือบเรียง

แนวเฉลยย่อ: เพราะแต่ละ key ต้องเลื่อนย้อนหลังไม่กี่ตำแหน่ง ลูป while จึงทำงานสั้นลงมาก ทำให้เวลารวมลดลงใกล้ O(n)

ฝึกลงมือจริงใน playground ต่อได้ใน Insertion Sort Lab ซึ่งมี 3 โจทย์ตามแบบฝึกข้างต้นและมี runtime checks ให้ตรวจผลทันที

ไปทำ Insertion Sort Lab

การค้นหาและการเรียงลำดับบทที่ 19Insertion Sort

Insertion Sort แบบละเอียดและเป็นระบบสำหรับผู้เริ่มต้น

1. Insertion Sort คืออะไร

2. เปรียบเทียบกับการเรียงไพ่ในมือ

Insertion Sort ทำงานเหมือนกันทุกประการ ต่างแค่ว่าเปลี่ยนจากไพ่เป็นสมาชิกใน array

3. หลักการแบ่งส่วนที่เรียงแล้วกับข้อมูลที่ยังไม่เรียง

4. ตัวอย่าง array เช่น [5, 2, 4, 6, 1, 3]

เราจะเรียงจากน้อยไปมาก โดยใช้อาเรย์ตัวอย่าง:[5, 2, 4, 6, 1, 3]

5. อธิบายการหยิบ key ออกมาแล้วเลื่อนสมาชิกที่มากกว่าไปทางขวา

6. อธิบายการแทรก key กลับเข้าไปในตำแหน่งที่ถูกต้อง

7. อธิบายทีละรอบอย่างละเอียด

8. Pseudocode

Pseudocode: Insertion Sortbash

โครงความคิดก่อนลงมือเขียนโค้ดจริง

ฟังก์ชัน 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 ไปทางขวา
      j = j - 1

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

  คืนค่า arr

9. ตัวอย่างโค้ด JavaScript พร้อมอธิบายทีละส่วน

JavaScript: Insertion SortJS

หยิบ key, เลื่อนค่าที่มากกว่า, แล้วแทรกกลับ

function insertionSort(values) {
  const arr = [...values]; // ไม่แก้ข้อมูลต้นฉบับโดยตรง

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

    // เลื่อนสมาชิกที่มากกว่า key ไปทางขวา
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j -= 1;
    }

    // แทรก key กลับในตำแหน่งที่เหมาะสม
    arr[j + 1] = key;
  }

  return arr;
}

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

10. Best / Average / Worst Time Complexity

Best: O(n)

เมื่อข้อมูลเรียงอยู่แล้ว ลูป while แทบไม่เลื่อนเลย

Average: O(n²)

โดยเฉลี่ยแต่ละ key ต้องเลื่อนผ่านสมาชิกหลายตัว

Worst: O(n²)

กรณีเรียงกลับด้าน key จะต้องเลื่อนไปเกือบสุดทุกครั้ง

ทำไมมักทำงานดีบนข้อมูลที่เกือบเรียงอยู่แล้ว

11. Space Complexity

12. ข้อดี

แนวคิดตรงไปตรงมาและเชื่อมโยงกับการเรียงไพ่ได้ง่าย

เป็นอัลกอริทึมแบบ stable (ค่าเท่ากันรักษาลำดับเดิมได้)

ทำงานดีบนข้อมูลขนาดเล็กหรือข้อมูลที่เกือบเรียงแล้ว

13. ข้อเสีย

เวลาเฉลี่ยและกรณีแย่ที่สุดเป็น O(n²) จึงไม่เหมาะกับข้อมูลขนาดใหญ่

เมื่อข้อมูลสลับตำแหน่งมาก จะมีการเลื่อนสมาชิกจำนวนมาก

ประสิทธิภาพโดยรวมแพ้อัลกอริทึมระดับ O(n log n) ในงานข้อมูลใหญ่

14. เหมาะกับกรณีไหน

15. เปรียบเทียบสั้น ๆ กับ Bubble Sort และ Selection Sort

เทียบกับ Bubble Sort

เทียบกับ Selection Sort

16. สรุปท้ายบท

17. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

ข้อ 1: เขียนฟังก์ชัน insertionSort(values) ให้เรียงจากน้อยไปมาก

ข้อ 2: ทำ Insertion Sort เพียง 1 รอบที่ i=4 กับ [2, 4, 5, 6, 1, 3]

แนวเฉลยย่อ: key = 1 เลื่อน 6,5,4,2 ไปขวา แล้วแทรก 1 ด้านหน้า ได้ [1, 2, 4, 5, 6, 3]

ข้อ 3: อธิบายว่าทำไม Insertion Sort ถึงเร็วขึ้นเมื่อข้อมูลเกือบเรียง

ไปทำ Insertion Sort Lab

Data Structures & Algorithms

Insertion Sort แบบละเอียดและเป็นระบบสำหรับผู้เริ่มต้น

1. Insertion Sort คืออะไร

2. เปรียบเทียบกับการเรียงไพ่ในมือ

3. หลักการแบ่งส่วนที่เรียงแล้วกับข้อมูลที่ยังไม่เรียง

4. ตัวอย่าง array เช่น [5, 2, 4, 6, 1, 3]

5. อธิบายการหยิบ key ออกมาแล้วเลื่อนสมาชิกที่มากกว่าไปทางขวา

6. อธิบายการแทรก key กลับเข้าไปในตำแหน่งที่ถูกต้อง

7. อธิบายทีละรอบอย่างละเอียด

8. Pseudocode

9. ตัวอย่างโค้ด JavaScript พร้อมอธิบายทีละส่วน

10. Best / Average / Worst Time Complexity

11. Space Complexity

12. ข้อดี

13. ข้อเสีย

14. เหมาะกับกรณีไหน

15. เปรียบเทียบสั้น ๆ กับ Bubble Sort และ Selection Sort

16. สรุปท้ายบท

17. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย

Loading

Data Structures & Algorithms

Insertion Sort แบบละเอียดและเป็นระบบสำหรับผู้เริ่มต้น

1. Insertion Sort คืออะไร

2. เปรียบเทียบกับการเรียงไพ่ในมือ

3. หลักการแบ่งส่วนที่เรียงแล้วกับข้อมูลที่ยังไม่เรียง

4. ตัวอย่าง array เช่น [5, 2, 4, 6, 1, 3]

5. อธิบายการหยิบ key ออกมาแล้วเลื่อนสมาชิกที่มากกว่าไปทางขวา

6. อธิบายการแทรก key กลับเข้าไปในตำแหน่งที่ถูกต้อง

7. อธิบายทีละรอบอย่างละเอียด

8. Pseudocode

9. ตัวอย่างโค้ด JavaScript พร้อมอธิบายทีละส่วน

10. Best / Average / Worst Time Complexity

11. Space Complexity

12. ข้อดี

13. ข้อเสีย

14. เหมาะกับกรณีไหน

15. เปรียบเทียบสั้น ๆ กับ Bubble Sort และ Selection Sort

16. สรุปท้ายบท

17. แบบฝึกหัด 3 ข้อ พร้อมแนวเฉลย