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

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

บทนี้จะพาเข้าใจการสลับค่าระหว่างสมาชิกที่อยู่ติดกันทีละคู่ และเห็นภาพชัดว่า ค่าที่มากกว่าจะค่อย ๆ ลอยไปทางขวาในแต่ละรอบ (pass)

1. Bubble Sort คืออะไร

Bubble Sort คืออัลกอริทึมเรียงข้อมูลที่ทำงานโดยเปรียบเทียบสมาชิกที่อยู่ติดกันทีละคู่ ถ้าคู่ไหนเรียงผิด (ตัวซ้ายมากกว่าตัวขวา) ก็สลับตำแหน่งทันที

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

2. แนวคิดการเปรียบเทียบสมาชิกที่อยู่ติดกัน

ในแต่ละรอบ เราจะดูคู่ (index j, j+1) เช่น (0,1), (1,2), (2,3) ไปเรื่อย ๆ แล้วถามคำถามเดียวคือ: “ตัวซ้ายมากกว่าตัวขวาหรือไม่”

ถ้าใช่ ให้สลับ ถ้าไม่ใช่ ก็ปล่อยผ่านแล้วเลื่อนไปคู่ถัดไป

3. ทำไมถึงชื่อ Bubble Sort

เพราะค่าใหญ่จะค่อย ๆ ขยับไปทางท้ายอาเรย์ทีละขั้น เหมือนฟองอากาศที่ค่อย ๆ ลอยขึ้น ในแต่ละ pass ค่ามากสุดที่ยังไม่ถูกจัดตำแหน่ง จะลอยไปอยู่ขวาสุดของช่วงที่ยังไม่เรียง

4. ตัวอย่างชีวิตจริงหรือภาพเปรียบเทียบ

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

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

เราจะเรียงจากน้อยไปมาก โดยเริ่มจากอาเรย์ [5, 3, 8, 4, 2]

ภาพแสดงการเปรียบเทียบและสลับสมาชิกที่อยู่ติดกันในแต่ละ pass ของ Bubble Sort

ค่ามากกว่าจะค่อย ๆ ลอยไปทางขวา

6. อธิบายการเปรียบเทียบและสลับทีละคู่ในรอบที่ 1

เริ่ม: [5, 3, 8, 4, 2] เปรียบเทียบ (5,3) พบว่า 5 > 3 จึงสลับ → [3, 5, 8, 4, 2]

เปรียบเทียบ (5,8) พบว่า 5 < 8 ไม่สลับ → [3, 5, 8, 4, 2]

เปรียบเทียบ (8,4) พบว่า 8 > 4 จึงสลับ → [3, 5, 4, 8, 2]

เปรียบเทียบ (8,2) พบว่า 8 > 2 จึงสลับ → [3, 5, 4, 2, 8] จบรอบที่ 1 และค่า 8 ลอยไปท้ายอาเรย์แล้ว

7. อธิบายต่อรอบที่ 2, 3, ... จนเรียงเสร็จ

รอบที่ 2 เริ่มจาก [3, 5, 4, 2, 8] เปรียบเทียบเฉพาะถึงก่อน 8: (3,5) ไม่สลับ, (5,4) สลับ, (5,2) สลับ ได้ผลลัพธ์ [3, 4, 2, 5, 8] และค่า 5 ไปอยู่ตำแหน่งที่ถูกต้อง

รอบที่ 3 เริ่มจาก [3, 4, 2, 5, 8] เปรียบเทียบ (3,4) ไม่สลับ, (4,2) สลับ ได้ [3, 2, 4, 5, 8] และค่า 4 เข้าที่

รอบที่ 4 เริ่มจาก [3, 2, 4, 5, 8] เปรียบเทียบ (3,2) สลับ → [2, 3, 4, 5, 8] ตอนนี้เรียงครบแล้ว

8. สรุปว่าแต่ละ pass ทำให้เกิดอะไร

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

9. Pseudocode

Pseudocode: Bubble Sortbash

โครงคิดก่อนเขียนโค้ดจริง

ฟังก์ชัน bubbleSort(values):
  n = จำนวนสมาชิกใน values

  ทำซ้ำ pass จาก 0 ถึง n - 2:
    ทำซ้ำ j จาก 0 ถึง n - 2 - pass:
      ถ้า values[j] > values[j + 1]:
        สลับ values[j] กับ values[j + 1]

  คืนค่า values

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Bubble Sort (พื้นฐาน)JS

เรียงจากน้อยไปมากด้วยการสลับสมาชิกที่อยู่ติดกัน

function bubbleSort(values) {
  const arr = [...values]; // ไม่แก้ของเดิมโดยตรง

  for (let pass = 0; pass < arr.length - 1; pass += 1) {
    for (let j = 0; j < arr.length - 1 - pass; j += 1) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2]));
// [2, 3, 4, 5, 8]

ลูปนอกควบคุมจำนวน pass และลูปในทำหน้าที่เปรียบเทียบสมาชิกติดกันทีละคู่ เมื่อเจอคู่ที่เรียงผิดจึงสลับตำแหน่ง

11. เวอร์ชัน optimized ด้วย swapped flag

JavaScript: Bubble Sort (แบบปรับปรุง)JS

ใช้ตัวแปร swapped เพื่อตรวจว่ารอบนั้นมีการสลับหรือไม่

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

  for (let pass = 0; pass < arr.length - 1; pass += 1) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1 - pass; j += 1) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    // ถ้า pass นี้ไม่มีการสลับ แปลว่าเรียงแล้ว จบได้เลย
    if (!swapped) break;
  }

  return arr;
}

console.log(bubbleSortOptimized([1, 2, 3, 4, 5]));
// [1, 2, 3, 4, 5] (จบเร็ว)

console.log(bubbleSortOptimized([5, 3, 8, 4, 2]));
// [2, 3, 4, 5, 8]

ถ้า pass ใดไม่มีการสลับเลย แปลว่าอาเรย์เรียงอยู่แล้ว สามารถหยุดได้ทันที ทำให้กรณีข้อมูลเกือบเรียงหรือเรียงอยู่แล้ว ทำงานเร็วขึ้นชัดเจน

12. กรณีดีที่สุด / เฉลี่ย / แย่ที่สุดของเวลา (Time Complexity)

Best: O(n)

เกิดเมื่อใช้งานเวอร์ชัน optimized และข้อมูลเรียงอยู่แล้ว

Average: O(n²)

โดยทั่วไปยังต้องเปรียบเทียบจำนวนมากในหลาย pass

Worst: O(n²)

เช่นข้อมูลเรียงกลับด้าน ต้องสลับจำนวนมากที่สุด

13. Space Complexity

ถ้าเรียงในอาเรย์เดิมแบบ in-place จะใช้หน่วยความจำเพิ่มเพียงตัวแปรชั่วคราวเล็กน้อย จึงมี Space Complexity เท่ากับ O(1)

14. ข้อดี

แนวคิดตรงไปตรงมา เหมาะสำหรับเริ่มต้นเรียนเรื่องการเรียงข้อมูล

เขียนโค้ดง่ายและดีสำหรับการฝึกตรรกะลูปซ้อน

เป็นอัลกอริทึมแบบ stable (ถ้าเขียนเงื่อนไขเปรียบเทียบอย่างถูกต้อง)

15. ข้อเสีย

ช้ามากเมื่อข้อมูลมีจำนวนมาก เพราะเวลาเฉลี่ยและแย่ที่สุดเป็น O(n²)

จำนวนการสลับอาจมาก ทำให้ต้นทุนสูงกว่าวิธีที่มีประสิทธิภาพกว่า

ในงานจริงมักมีตัวเลือกที่เร็วกว่า เช่น Merge Sort หรือ Quick Sort

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

เหมาะกับการสอนพื้นฐานอัลกอริทึม, ข้อมูลขนาดเล็ก, หรือสถานการณ์ที่ต้องการโค้ดสั้น ๆ เพื่ออธิบายหลักการเปรียบเทียบและสลับค่าก่อนเรียนวิธีที่ซับซ้อนขึ้น

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

ไม่เหมาะกับข้อมูลขนาดใหญ่หรือระบบที่ต้องการประสิทธิภาพสูง เพราะ O(n²) ทำให้ใช้เวลานานกว่าวิธีที่ดีกว่าอย่างชัดเจน

18. สรุปท้ายบทแบบจำง่าย

จำสั้น ๆ ว่า Bubble Sort คือ “เทียบคู่ติดกัน ถ้าผิดก็สลับ” ทำซ้ำหลาย pass จนค่ามากค่อย ๆ ลอยไปทางขวาและอาเรย์เรียงครบ

ถ้าต้องการให้เร็วขึ้นในกรณีข้อมูลเกือบเรียง ใช้เวอร์ชัน optimized ที่มีswapped flagเพื่อหยุดก่อนครบทุก pass

19. โจทย์ฝึกใน Playground พร้อมระบบตรวจอัตโนมัติ

ฝึกต่อด้วย Bubble Sort Lab ที่มี 3 โจทย์: bubbleSort พื้นฐาน, bubbleSortPass (ทำ 1 pass) และ bubbleSortOptimized ด้วย swapped flag โดยแต่ละโจทย์มี runtime checks หลายเคสให้ตรวจผลได้ทันที

ไปทำ Bubble Sort Lab

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

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

1. Bubble Sort คืออะไร

2. แนวคิดการเปรียบเทียบสมาชิกที่อยู่ติดกัน

ถ้าใช่ ให้สลับ ถ้าไม่ใช่ ก็ปล่อยผ่านแล้วเลื่อนไปคู่ถัดไป

3. ทำไมถึงชื่อ Bubble Sort

4. ตัวอย่างชีวิตจริงหรือภาพเปรียบเทียบ

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

เราจะเรียงจากน้อยไปมาก โดยเริ่มจากอาเรย์ [5, 3, 8, 4, 2]

ค่ามากกว่าจะค่อย ๆ ลอยไปทางขวา

6. อธิบายการเปรียบเทียบและสลับทีละคู่ในรอบที่ 1

เริ่ม: [5, 3, 8, 4, 2] เปรียบเทียบ (5,3) พบว่า 5 > 3 จึงสลับ → [3, 5, 8, 4, 2]

เปรียบเทียบ (5,8) พบว่า 5 < 8 ไม่สลับ → [3, 5, 8, 4, 2]

เปรียบเทียบ (8,4) พบว่า 8 > 4 จึงสลับ → [3, 5, 4, 8, 2]

7. อธิบายต่อรอบที่ 2, 3, ... จนเรียงเสร็จ

รอบที่ 4 เริ่มจาก [3, 2, 4, 5, 8] เปรียบเทียบ (3,2) สลับ → [2, 3, 4, 5, 8] ตอนนี้เรียงครบแล้ว

8. สรุปว่าแต่ละ pass ทำให้เกิดอะไร

9. Pseudocode

Pseudocode: Bubble Sortbash

โครงคิดก่อนเขียนโค้ดจริง

ฟังก์ชัน bubbleSort(values):
  n = จำนวนสมาชิกใน values

  ทำซ้ำ pass จาก 0 ถึง n - 2:
    ทำซ้ำ j จาก 0 ถึง n - 2 - pass:
      ถ้า values[j] > values[j + 1]:
        สลับ values[j] กับ values[j + 1]

  คืนค่า values

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

JavaScript: Bubble Sort (พื้นฐาน)JS

เรียงจากน้อยไปมากด้วยการสลับสมาชิกที่อยู่ติดกัน

function bubbleSort(values) {
  const arr = [...values]; // ไม่แก้ของเดิมโดยตรง

  for (let pass = 0; pass < arr.length - 1; pass += 1) {
    for (let j = 0; j < arr.length - 1 - pass; j += 1) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2]));
// [2, 3, 4, 5, 8]

11. เวอร์ชัน optimized ด้วย swapped flag

JavaScript: Bubble Sort (แบบปรับปรุง)JS

ใช้ตัวแปร swapped เพื่อตรวจว่ารอบนั้นมีการสลับหรือไม่

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

  for (let pass = 0; pass < arr.length - 1; pass += 1) {
    let swapped = false;

    for (let j = 0; j < arr.length - 1 - pass; j += 1) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }

    // ถ้า pass นี้ไม่มีการสลับ แปลว่าเรียงแล้ว จบได้เลย
    if (!swapped) break;
  }

  return arr;
}

console.log(bubbleSortOptimized([1, 2, 3, 4, 5]));
// [1, 2, 3, 4, 5] (จบเร็ว)

console.log(bubbleSortOptimized([5, 3, 8, 4, 2]));
// [2, 3, 4, 5, 8]

12. กรณีดีที่สุด / เฉลี่ย / แย่ที่สุดของเวลา (Time Complexity)

Best: O(n)

เกิดเมื่อใช้งานเวอร์ชัน optimized และข้อมูลเรียงอยู่แล้ว

Average: O(n²)

โดยทั่วไปยังต้องเปรียบเทียบจำนวนมากในหลาย pass

Worst: O(n²)

เช่นข้อมูลเรียงกลับด้าน ต้องสลับจำนวนมากที่สุด

13. Space Complexity

14. ข้อดี

แนวคิดตรงไปตรงมา เหมาะสำหรับเริ่มต้นเรียนเรื่องการเรียงข้อมูล

เขียนโค้ดง่ายและดีสำหรับการฝึกตรรกะลูปซ้อน

เป็นอัลกอริทึมแบบ stable (ถ้าเขียนเงื่อนไขเปรียบเทียบอย่างถูกต้อง)

15. ข้อเสีย

ช้ามากเมื่อข้อมูลมีจำนวนมาก เพราะเวลาเฉลี่ยและแย่ที่สุดเป็น O(n²)

จำนวนการสลับอาจมาก ทำให้ต้นทุนสูงกว่าวิธีที่มีประสิทธิภาพกว่า

ในงานจริงมักมีตัวเลือกที่เร็วกว่า เช่น Merge Sort หรือ Quick Sort

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

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

18. สรุปท้ายบทแบบจำง่าย

19. โจทย์ฝึกใน Playground พร้อมระบบตรวจอัตโนมัติ

ไปทำ Bubble Sort Lab

Data Structures & Algorithms

1. Bubble Sort คืออะไร

2. แนวคิดการเปรียบเทียบสมาชิกที่อยู่ติดกัน

3. ทำไมถึงชื่อ Bubble Sort

4. ตัวอย่างชีวิตจริงหรือภาพเปรียบเทียบ

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

6. อธิบายการเปรียบเทียบและสลับทีละคู่ในรอบที่ 1

7. อธิบายต่อรอบที่ 2, 3, ... จนเรียงเสร็จ

8. สรุปว่าแต่ละ pass ทำให้เกิดอะไร

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. เวอร์ชัน optimized ด้วย swapped flag

12. กรณีดีที่สุด / เฉลี่ย / แย่ที่สุดของเวลา (Time Complexity)

13. Space Complexity

14. ข้อดี

15. ข้อเสีย

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

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

18. สรุปท้ายบทแบบจำง่าย

19. โจทย์ฝึกใน Playground พร้อมระบบตรวจอัตโนมัติ

Loading

Data Structures & Algorithms

1. Bubble Sort คืออะไร

2. แนวคิดการเปรียบเทียบสมาชิกที่อยู่ติดกัน

3. ทำไมถึงชื่อ Bubble Sort

4. ตัวอย่างชีวิตจริงหรือภาพเปรียบเทียบ

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

6. อธิบายการเปรียบเทียบและสลับทีละคู่ในรอบที่ 1

7. อธิบายต่อรอบที่ 2, 3, ... จนเรียงเสร็จ

8. สรุปว่าแต่ละ pass ทำให้เกิดอะไร

9. Pseudocode

10. ตัวอย่างโค้ด JavaScript พร้อมคำอธิบาย

11. เวอร์ชัน optimized ด้วย swapped flag

12. กรณีดีที่สุด / เฉลี่ย / แย่ที่สุดของเวลา (Time Complexity)

13. Space Complexity

14. ข้อดี

15. ข้อเสีย

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

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

18. สรุปท้ายบทแบบจำง่าย

19. โจทย์ฝึกใน Playground พร้อมระบบตรวจอัตโนมัติ