昨天終於用 TypeScript 寫出了 Quick Sort，今天準備把它放進 Vue，讓排序過程像之前的 Bubble Sort 一樣動起來。

前面實作 Bubble Sort 視覺化時，我已經知道如果想讓演算法一步一步播放，就需要把執行過程中的狀態一個一個記錄成「快照」。

所以今天先不急著寫動畫，而是先想：

Quick Sort 的一張快照，到底需要記錄哪些狀態？

一開始我覺得這些狀態應該就夠了

回頭看昨天的 Quick Sort，主要就是選擇 Pivot，再把資料分成小於、等於、大於 Pivot 三個區域。

所以一開始我先列出：

type QuickSortStep = {
  phase: 'start' | 'pivot' | 'compare' | 'partition' | 'complete' // 目前進行到哪個階段
  current: number | null //// 目前正在跟 Pivot 比較的值
  pivot: number | null // 目前 Pivot
  less: number[] //已被分到「比 Pivot 小」的值
  equal: number[] //已被分到「與 Pivot 相等」的值
  more: number[] // 已被分到「比 Pivot 大」的值
  description: string // 顯示目前步驟的文字說明
}

看起來好像差不多了，但開始思考這些資料要怎麼控制 Vue 的長條圖後，就發現還少了不少東西。

遇到相同數值，要怎麼知道是哪一根 Bar？

假設資料是：

[5, 3, 5, 8, 3]

如果只記錄 current = 5，畫面上有兩個 5，Vue 要怎麼知道現在比較的是哪一個？

所以比起只存數值，我還需要 記錄位置：

currentIndex
lessIndexes
equalIndexes
moreIndexes

這樣才能準確控制哪一根 Bar 要改變狀態。

現在到底正在處理哪一段？

Quick Sort 會一直遞迴，第一次可能處理完整陣列，下一次卻只處理其中的 lessArr。

但畫面上的其他 Bar 並不會消失，所以還需要：

startIndex // 目前遞迴處理範圍的起點
endIndex // 目前遞迴處理範圍的終點

用來告訴 Vue：

「這次 Quick Sort 處理的是完整陣列中的這個範圍。」

為什麼還需要完整的 arr？

這也是我一開始最疑惑的地方。

例如：

[17, 3, 42, 8]

第一次切分後：

lessArr = [3, 8]
pivot = [17]
moreArr = [42]

接著執行：

quickSort(lessArr)

這一層的 arr 就只剩 [3, 8]。

但我的 Vue 長條圖不能跟著只剩兩根 Bar，畫面還是要保留完整資料，只是把目前處理的區域標示出來。

因此快照還需要保存完整的 arr：

<div
  v-for="(num, index) in currentStep.arr"
  :key="index"
>
  {{ num }}
</div>

簡單來說：

arr 決定畫面「要顯示哪些 Bar」，其他狀態則決定「這些 Bar 要怎麼顯示」。

最後整理出來的快照狀態

經過上面的問題後，原本的狀態就變成：

type QuickSortStep = {
  arr: number[] // 畫面目前顯示的完整陣列

  phase: 'start' | 'pivot' | 'compare' | 'partition' | 'complete' // 目前進行到哪個階段

  pivotIndex: number | null // 目前 Pivot 在陣列中的位置
  currentIndex: number | null // 目前正在跟 Pivot 比較的位置

  startIndex: number // 目前遞迴處理範圍的起點
  endIndex: number // 目前遞迴處理範圍的終點

  lessIndexes: number[] // 已被分到「比 Pivot 小」的位置
  equalIndexes: number[] // 已被分到「與 Pivot 相等」的位置
  moreIndexes: number[] // 已被分到「比 Pivot 大」的位置

  description: string // 顯示目前步驟的文字說明
}

原本以為做過 Bubble Sort 視覺化後，Quick Sort 應該只要多標示一個 Pivot 就好，實際拆解後才發現，因為多了 Partition 和遞迴，需要記錄的畫面狀態也更多。

今天先解決 「一張快照要記錄什麼？」，下一個問題就是：

這些快照到底要在 Quick Sort 的哪些地方建立？