昨天已經先整理好 Quick Sort 一張快照需要記錄哪些狀態，今天就要回到 Day 13 寫好的 Quick Sort ，開始思考另一個問題：

到底要在哪些時間點記錄快照？

一開始我的想法很單純，只要程式有變化，好像就應該記一張快照，所以我先直接用註解標出可能的位置：

const quickSort = (arr: number[]) => {
  // 快照：剛開始
  const pivot = [arr[0]] as number[]

  // 快照：設定基準值
  const lessArr = [] as number[]
  const moreArr = [] as number[]

  if (arr.length <= 1) {
    // 快照：目前只剩一個值或已經沒有值
    return arr
  }

  // 快照：開始分類
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot[0]) {
      // 快照：arr[i] 小於 pivot
      lessArr.push(arr[i])
      // 快照：放入 lessArr
    }

    if (arr[i] > pivot[0]) {
      // 快照：arr[i] 大於 pivot
      moreArr.push(arr[i])
      // 快照：放入 moreArr
    }

    if (arr[i] === pivot[0]) {
      // 快照：arr[i] 等於 pivot
      pivot.push(arr[i])
      // 快照：放入 pivot
    }
  }

  // 快照：目前分類結果
  return [
    ...quickSort(lessArr),
    ...pivot,
    ...quickSort(moreArr)
  ]
}

但每個動作都需要快照嗎？

重新看一次後，我發現如果「比較前」記一次、「比較後」又記一次、「push 完」再記一次，雖然非常完整，但動畫可能會被切得太細。

例如：

if (arr[i] < pivot[0]) {
  lessArr.push(arr[i])
}

對畫面來說，我真正想呈現的是：

目前正在比較哪個數字，以及比較完成後它被分類到哪裡。

所以不一定每一行程式碼都需要一張快照，而是應該從「使用者需要看到什麼變化」來決定。

目前我把主要過程整理成：

選擇 Pivot → 比較 → 分類 → 分割完成 → Base Case → 合併完成

原本的 return 還有一個問題

原本我是直接：

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

但這一行其實同時做了好幾件事情：

遞迴排序左邊 → 遞迴排序右邊 → 最後把結果組合起來。

如果直接 return，我也沒有機會記錄「這一層已經合併完成」的快照。

所以我決定先把結果拆開：

const lessResult = quickSort(lessArr)
const moreResult = quickSort(moreArr)

const result = [
  ...lessResult,
  ...pivot,
  ...moreResult
]

// 快照：這一層合併完成

return result

例如 [5, 3, 8, 1] 第一層會先拆成：

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

接著 [3, 1] 繼續遞迴，最後得到：

lessResult = [1, 3]
moreResult = [8]

再把它們組合：

[1, 3] + [5] + [8]
        ↓
[1, 3, 5, 8]

這個「組合完成」，就是我一開始漏掉的重要快照。

最後決定記錄哪些時間點？

整理完後，我目前預計把快照集中在幾個真正會影響畫面的階段：

const quickSort = (arr: number[]) => {
  if (arr.length <= 1) {
    // 快照：Base Case
    return arr
  }

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

  // 快照：選擇 Pivot

  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])
    }

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

    // 快照：分類完成
  }

  // 快照：這一層分割完成

  const lessResult = quickSort(lessArr)
  const moreResult = quickSort(moreArr)

  const result = [
    ...lessResult,
    ...pivot,
    ...moreResult
  ]

  // 快照：這一層合併完成

  return result
}

這樣整理後，我目前需要的快照大致可以分成：

1. Base Case：目前只剩一個元素或空陣列，不需要再繼續拆分。
2. 選擇 Pivot：標示這一輪使用的基準值。
3. 比較：目前正在拿哪個元素與 Pivot 比較。
4. 分類完成：元素被放進 lessArr、pivot 或 moreArr。
5. 分割完成：這一輪所有元素都已經分類完畢。
6. 合併完成：左右兩邊遞迴完成後，重新組合出這一層的結果。

今天最大的發現

原本我以為做演算法動畫，就是程式執行到哪裡，就把那一刻全部記錄下來。

但真的開始規劃之後才發現：

快照不是程式每執行一行就記一次，而是畫面真正需要呈現「狀態變化」時才記錄。

記得太少，使用者可能看不懂中間發生什麼事；但記得太細，動畫又會出現很多幾乎沒有變化的畫面。

現在已經知道「快照要存什麼」以及「什麼時候存」，下一步就可以真的把這些快照建立起來，看看 Quick Sort 的遞迴過程能不能一步一步顯示在畫面上。