การ Implement Quick Sort ใน JavaScript

Quick Sort - Divide and Conquer

Quick Sort เลือก Pivot แบ่ง Array เป็น 2 ส่วน: น้อยกว่า Pivot และ มากกว่า Pivot แล้ว Recursive Sort แต่ละส่วน

Implementation (Lomuto Partition)

<script>
  function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[arr.length - 1]; // เลือกตัวสุดท้ายเป็น Pivot
    const left = [];
    const right = [];
    
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] <= pivot) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    
    return [...quickSort(left), pivot, ...quickSort(right)];
  }
  
  const myArray = [9, 0, 2, 7, -2, 6, 1];
  console.log('Original:', myArray);
  console.log('Sorted:', quickSort(myArray));
  // Original: [9, 0, 2, 7, -2, 6, 1]
  // Sorted: [-2, 0, 1, 2, 6, 7, 9]
</script>

In-place Version (Space O(log n))

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSortInPlace(arr, low, pi - 1);
    quickSortInPlace(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

Complexity

Pivot Selection Strategies

• Last Element: เรียบง่าย แต่ Worst Case บน Sorted Array
• Random: หลีกเลี่ยง Worst Case
• Median-of-Three: Median ของ First, Middle, Last

Quick Sort vs Merge Sort

• Quick Sort: In-place, Cache-friendly, Unstable, Worst O(n²)
• Merge Sort: Stable, Guaranteed O(n log n), Extra Space O(n)