QuickSort แบบ Divide & Conquer - JavaScript

การเรียงลำดับ QuickSort: อัลกอริทึมแบ่งแยกและเอาชนะ (Divide & Conquer) เลือก pivot แล้ววางค่าน้อยกว่าซ้าย มากกว่าขวา เรียกซ้ำ

ตัวอย่างโค้ด

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, 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]];
      i++; j--;
    }
  }
  return i;
};

console.log(quickSort(arr));

ผลลัพธ์

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

การวิเคราะห์

การปรับปรุง: Randomized Pivot

const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
const pivot = arr[pivotIndex];

ป้องกัน worst case บนข้อมูลที่เรียงลำดับแล้ว