昨天把 Quick Sort 改成 Lomuto Partition 後，今天終於可以回頭實作 Day 14、15 規劃的快照。

原本以為前面已經想好「快照要記什麼」，真正開始寫才發現：換成 Lomuto 之後，需要記錄的狀態比我原本想像中還要多。

最後我把 Quick Sort 的快照分成：

start → pivot → compare → swap → partition → done

接下來最大的問題就是：一張快照到底要知道多少事情？

一張快照要記多少狀態？

最後我整理出：

low
high
pivotIndex
boundary
scanned
comparingIndex

low / high 是目前遞迴處理的範圍，pivotIndex 是 Pivot 的位置，comparingIndex 則是現在正在跟 Pivot 比較的位置。

真正實作後才多想到的是 boundary 和 scanned。

boundary 對應 Lomuto 裡的 i，代表目前「小於 Pivot」的區域到哪裡；scanned 則代表目前已經掃描完成到哪個位置。

因為畫面不只要知道「現在比較誰」，還要知道：前面處理到哪裡，以及現在的分界線在哪裡。

最讓我混亂的是 Array 一直在交換

除了要追蹤邊界，我覺得實作時另一個很容易亂掉的地方，就是 Lomuto 會直接修改同一組 Array。

像我實際寫到比較、交換這段時：

let i = low

for (let j = low; j < high; j++) {
  const value = arr[j] ?? 0

  push({ phase: 'compare', ... })

  if (value < pivot) {
    if (i !== j) {
      const moved = arr[i] ?? 0

      arr[i] = value
      arr[j] = moved

      push({ phase: 'swap', ... })
    }

    i++
  }
}

單看 Quick Sort 的流程，我知道 j 是一路往右找比 Pivot 小的數字，i 則是記住下一個較小數字要放的位置。

但真的寫成程式碼後，就開始有點混亂了。

因為我不只要記得現在 i、j 在哪裡，還要注意：

value 是誰？moved 又是誰？交換之後 Array 變成什麼？i 什麼時候要往右移？

而且中間還要插入：

push({ phase: 'compare', ... })

push({ phase: 'swap', ... })

來記錄不同時間點的畫面。

所以這時候我才發現，Quick Sort 做成視覺化後，困難的已經不只是「會不會交換」，而是交換的同時，我還得記住當下所有狀態，才能知道這張快照到底要畫什麼。

已經處理好的位置也要記住

做到遞迴後，我又遇到另一個原本沒想到的問題。

每次 Partition 完成後，Pivot 的位置就已經確定了。但進入下一層遞迴，low / high 會變成新的區間，如果只看目前正在處理的範圍，前面已經定位的長條就可能又變回預設狀態。

所以我另外建立：

const placed = new Set<number>()

每當 Pivot 確定位置，就把 index 加進 placed：

placed.add(i)

這樣即使接下來跑到其他子陣列，前面已經完成的長條還是可以維持 sorted。

原來除了記錄「現在正在發生什麼」，還需要保存前面已經完成了什麼。

Quick Sort 實作完成

做到這裡，再回頭看前幾章對於「快照」的理解還比較單純。

真正實作 Lomuto 後，我才發現除了記錄當下正在做什麼，還得一直追蹤分界線、掃描進度，以及前面已經定位的位置。

尤其 i、j 一直移動，Array 裡的數字又不斷交換、重新賦值，這些狀態全部疊在一起時，真的很容易混亂。

但也因為真的把它做成畫面，我才開始理解：演算法視覺化真正困難的地方，不只是把演算法寫出來，而是怎麼把程式執行中看不到的狀態保存下來，再轉換成畫面看得懂的資訊。