11.md

Quick Sort

Definition

使用了 Partition 演算法，先指定 array 的最後一個值為 Pivot，將所有小於 Pivot 的值歸類為一群，反之大於為一群（同一群的數值必須再一起，所以需要互換）。當 array 做完 Partition 之後就可觀察到 Pivot 已經被排序了並且分成兩群。然後在兩個群組之內繼續做 Partition 演算法，即可得知。

Performance

• Worst Case: O(n^2)
• Best Case: O(nlogn)
• Average Case: O(nlogn)

Code:

const arr = [15, 3, 17, 18, 20, 2, 1, 666];

function partition(p, r) {
  let x = arr[r]; // Pivot
  let i = p - 1; // 有多算數字小於 Pivot
  for (let j = p; j <= r - 1; j++) {
    if (arr[j] <= x) {
      i += 1; // 有一個小於 Pivot
      // Swap arr[i] and arr[j]
      const temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  // Swap arr[i+1] and arr[r] 表示跑完整個 array，需要把 Pivot 移動至 i+1 位置
  const temp = arr[i + 1];
  arr[i + 1] = arr[r];
  arr[r] = temp;
  return i + 1;
}

function quickSort(p, r) {
  if (p < r) {
    const q = partition(p, r);
    quickSort(p, q - 1); // 左邊群組在做一次 quick sort
    quickSort(q + 1, r); // 右邊群組在做一次 quick sort
  }
}

quickSort(0, arr.length - 1);
console.log(arr);