前兩天已經整理好 Quick Sort 的「快照要記什麼」以及「什麼時候記」，原本以為今天終於可以直接開始實作動畫。

但真的開始寫之後，我才發現一個問題：

我原本學會的 Quick Sort 寫法，雖然可以完成排序，卻不太適合現在的長條圖動畫。

原本的 Quick Sort 有什麼問題？

Day 13 寫的版本，是先選出 pivot，再建立 lessArr、moreArr：

const pivot = [arr[0]] as number[]
const lessArr = [] as number[]
const moreArr = [] as number[]

for (let i = 1; i < arr.length; i++) {
  if (arr[i] < pivot[0]) {
    lessArr.push(arr[i])
  }

  if (arr[i] > pivot[0]) {
    moreArr.push(arr[i])
  }
}

最後再遞迴：

return [
  ...quickSort(lessArr),
  ...pivot,
  ...quickSort(moreArr)
]

這個寫法在理解 Quick Sort 時很直覺，因為真的可以看到：

比 pivot 小 → 放左邊
pivot → 放中間
比 pivot 大 → 放右邊

但動畫真正需要的，不只是「數字被分到哪一邊」，還要知道：

這個數字現在位於原本陣列的哪個 index？

問題就在這裡。

每次進入遞迴，我都會建立新的 lessArr、moreArr，index 也會跟著重新從 0 開始。

例如原本：

[5, 3, 8, 1]

第一次分割後：

lessArr = [3, 1]
pivot = [5]
moreArr = [8]

原本的 1 在 index 3，進入 lessArr 後卻變成 index 1。

對排序本身沒有問題，但對我的動畫來說就麻煩了。

因為畫面上的長條是依照同一組 Array 的 index 顯示，我希望可以持續追蹤：

「現在比較哪一根？哪兩根交換？Pivot 最後停在哪裡？」

如果每次遞迴都換成新的 Array，這些位置就很難一路對應下去。

所以我改成 Lomuto Partition

最後我決定改成 Lomuto Partition（Lomuto 分割法）。

這個版本最大的不同是：不另外建立 lessArr、moreArr，而是在原本的 Array 裡直接交換位置。

function quickSort(
  arr: number[],
  low = 0,
  high = arr.length - 1
) {
  if (low >= high) return arr

  const pivot = arr[high]
  let i = low

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      i++
    }
  }

  [arr[i], arr[high]] = [arr[high], arr[i]]

  quickSort(arr, low, i - 1)
  quickSort(arr, i + 1, high)

  return arr
}

這次我把最右邊的數字當成 pivot。

其中有兩個目前對動畫很重要的 index：

• j：目前掃描、正在跟 pivot 比較的位置
• i：分界線，也是下一個「比 pivot 小的數字」應該放的位置

當 arr[j] < pivot 時，就把 arr[j] 和 arr[i] 交換。

掃描結束後，再把 pivot 跟 arr[i] 交換，pivot 就會來到這一次分割後應該在的位置。

為什麼最後選擇這個版本？

這兩種 Quick Sort 寫法 適合的目的不一樣。

原本建立 lessArr / moreArr 的版本，我覺得比較容易理解 Quick Sort「分割 → 遞迴 → 合併」的概念，所以前面拿來學習很適合。

但現在我要做的是動畫。

改成 Lomuto 之後，Array 從頭到尾都是同一組資料，我可以直接利用 index 記錄：

目前處理區間 → Pivot 在哪裡 → j 比較到哪裡 → i 的分界線在哪裡 → 哪兩個位置發生交換

這些資訊剛好也是長條動畫需要知道的狀態。

而且右側顯示的 Quick Sort Code，也可以直接跟真正執行的程式同步高亮，不需要為了動畫另外解釋另一套邏輯。

前兩天設計的快照要全部重來嗎？

一開始發現要換 Quick Sort 寫法時，我其實有點擔心 Day 15、16 白做了。

但重新整理後發現，其實沒有。

前面決定的：

選擇 Pivot → Compare → 分割 → Base Case → 完成

這些「動畫階段」還是存在。

真正改變的是：

每張快照要用什麼資料描述目前畫面。

原本可能想記錄 lessArr、pivot、moreArr，現在則可以改成記錄：

low
high
pivotIndex
i
j
comparingIndex

也就是從「記錄產生了哪些新陣列」，變成「記錄原陣列目前哪些 index 正在做什麼」。

這反而更符合我一開始想做的長條動畫。

今天的小結

今天原本只是想開始把 Quick Sort 快照真正寫出來，沒想到第一步卻是先把演算法換掉。

也讓我發現：演算法能把結果算對，不代表它就一定適合拿來做視覺化。

原本的 lessArr / moreArr 寫法很適合幫助我理解 Quick Sort；但到了動畫實作階段，我更需要的是「位置可以被持續追蹤」。

所以最後改成 Lomuto Partition，讓所有操作都發生在同一個 Array 裡。

接下來，就可以利用 low、high、i、j 和 pivotIndex，真正開始建立 Quick Sort 的每一步快照了。

參考資料

Google Search，〈Quick Sort〉
https://www.google.com/search?sca_esv=f6e9261401242892&sxsrf=APpeQnsoUfvME2ol4SxoUKbERuA0Wm1DTw:1790048520902&udm=vids&q=quick+Sort