การจัดเรียงอาร์เรย์ด้วย Quick Sort ใน JavaScript

ภาพรวม

Quick Sort เป็นอัลกอริทึมการจัดเรียงแบบ "แบ่งและเอาชนะ" (Divide and Conquer) ที่มีประสิทธิภาพสูง ความซับซ้อนเฉลี่ยคือ O(n log n)

หลักการทำงาน

1. เลือก Pivot (ส่วนมากเลือกค่ากึ่งกลาง)
2. แบ่งอาร์เรย์: ค่าน้อยกว่า Pivot วางซ้าย ค่ามากกว่า Pivot วางขวา
3. เรียกฟังก์ชันซ้ำ (Recursive) กับส่วนซ้ายและขวา จนกว่าจะจัดเรียงเสร็จ

การนำไปใช้

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    const index = partition(arr, left, right);
    quickSort(arr, left, index - 1);
    quickSort(arr, index, right);
  }
  return arr;
};

const partition = (arr, left, right) => {
  const middle = Math.floor((left + right) / 2);
  const pivot = arr[middle];
  let i = left;
  let j = right;

  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; // ES6 Destructuring Swap
      i++;
      j--;
    }
  }
  return i;
};

console.log(quickSort(arr));

ผลลัพธ์

[2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434]

ข้อสังเกตสำคัญ

• การเลือก Pivot ส่งผลต่อประสิทธิภาพ: เลือกค่ากึ่งกลางหรือสุ่ม จะลดโอกาส worst-case (O(n²))
• Quick Sort เป็น In-place Sorting (ไม่ต้องการหน่วยความจำเพิ่มมากนัก)
• ไม่เสถียร (Unstable): ตัวเลขซ้ำอาจสลับตำแหน่งกัน

ตัวเลือกอื่นใน JavaScript

สำหรับการใช้งานจริง แนะนำให้ใช้ Array.prototype.sort() ตัวในตัว ซึ่งใช้ Timsort (Hybrid của Merge Sort และ Insertion Sort) ที่มีประสิทธิภาพดีและเสถียร:

arr.sort((a, b) => a - b);