Basic Sorting

รู้จัก Bubble Sort

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

หัวใจของ Bubble Sort เรียบง่ายมาก: "เทียบคู่ติดกัน ถ้าผิดก็สลับ" ทำซ้ำหลาย pass จนกว่าทั้งอาเรย์จะเรียงถูกต้อง

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

ทำไมถึงชื่อ Bubble Sort และภาพจำจากชีวิตจริง

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

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

ค่ามากกว่าจะค่อย ๆ ลอยไปทางขวาในแต่ละ pass — เหมือนฟองอากาศลอยขึ้น

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

เราจะสาธิตด้วยอาเรย์ [5, 3, 8, 4, 2] โดยเป้าหมายคือเรียงจากน้อยไปมาก มาดูกันว่าเกิดอะไรขึ้นในแต่ละ pass

• **Pass 1:** เริ่ม [5,3,8,4,2] → (5,3) สลับเป็น [3,5,8,4,2] → (5,8) ไม่สลับ → (8,4) สลับเป็น [3,5,4,8,2] → (8,2) สลับเป็น [3,5,4,2,8] จบ pass 1 ค่า 8 อยู่ขวาสุดแล้ว
• **Pass 2:** เริ่ม [3,5,4,2,8] เปรียบเทียบแค่ถึงก่อน 8 → (3,5) ไม่สลับ → (5,4) สลับเป็น [3,4,5,2,8] → (5,2) สลับเป็น [3,4,2,5,8] จบ pass 2 ค่า 5 เข้าที่
• **Pass 3:** เริ่ม [3,4,2,5,8] → (3,4) ไม่สลับ → (4,2) สลับเป็น [3,2,4,5,8] จบ pass 3 ค่า 4 เข้าที่
• **Pass 4:** เริ่ม [3,2,4,5,8] → (3,2) สลับเป็น [2,3,4,5,8] เรียงสมบูรณ์ — เหลือ 1 pass โดยไม่มีการสลับเพื่อยืนยัน

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

Pseudocode และโค้ด JavaScript

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

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

  คืนค่า values

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]

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

Bubble Sort แบบ Optimized ด้วย swapped flag

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;
      }
    }

    if (!swapped) break;
  }

  return arr;
}

console.log(bubbleSortOptimized([1, 2, 3, 4, 5]));
// [1, 2, 3, 4, 5] — จบเร็วมากหลัง pass แรก
console.log(bubbleSortOptimized([5, 3, 8, 4, 2]));
// [2, 3, 4, 5, 8]

ข้อดีของเวอร์ชัน optimized: ถ้าข้อมูลเกือบเรียงหรือเรียงอยู่แล้ว (Best Case) จะเหลือ Time Complexity เพียง O(n) เพราะ loop นอกจบตั้งแต่ pass แรก — เร็วกว่าเวอร์ชันพื้นฐานที่ต้องทำ n-1 pass เสมอ

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

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

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

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

• Best Case: O(n) — ข้อมูลเรียงอยู่แล้ว เวอร์ชัน optimized จะจบตั้งแต่ pass แรก (ทำ n-1 ครั้ง ไม่สลับเลย)
• Average Case: O(n²) — โดยทั่วไปยังต้องเปรียบเทียบในลูปซ้อนประมาณ n(n-1)/2 ครั้ง
• Worst Case: O(n²) — ข้อมูลเรียงกลับด้าน (เช่น [5,4,3,2,1]) ต้องสลับมากที่สุด ≈ n(n-1)/2 ครั้ง

Space Complexity = O(1) — Bubble Sort เป็น in-place algorithm ใช้ตัวแปรชั่วคราว (temp, swapped) เพียงเล็กน้อยเท่านั้น ไม่ต้องสร้างโครงสร้างข้อมูลใหม่

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

เปรียบเทียบกับ Selection Sort และ Insertion Sort

Bubble Sort, Selection Sort และ Insertion Sort เป็น 3 อัลกอริทึมเรียงข้อมูลพื้นฐานที่ใช้แนวคิดต่างกัน — ตารางนี้ช่วยให้คุณเลือกใช้ได้ถูกต้องตามสถานการณ์

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

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