關於此實驗
觀察泡沫排序、插入排序和合併排序如何將相同輸入轉換為升冪。你可以在比較時暫停、逐步查看每次寫入，也可以沿著完整軌跡向後移動。分別統計值比較次數和主陣列寫入次數，有助於區分演算法的工作量與動畫播放時間。
學習目標
- 追蹤三種比較排序演算法中的比較和寫入
- 比較演算法在亂序、已排序和反向排序輸入上的效能
- 區分最壞情況下的二次成長與 n log n 成長
使用方法
- 1固定亂序輸入和陣列長度。執行完泡沫排序，並記錄比較次數和寫入次數。
- 2使用相同輸入重新執行插入排序，接著執行合併排序。比較最終計數。
- 3嘗試已排序的輸入，觀察泡沫排序的提早結束，以及插入排序較少的比較次數。
- 4使用「Previous」和軌跡滑桿查看合併過程。暫存緩衝區可以保存那些在原本主陣列位置上已不可見的值。
模型
假設
- 輸入包含從 1 到 n 的不重複整數。打亂資料時使用固定種子，因此每種演算法接收的資料都相同。
- 比較是測試資料值，而不是測試索引或迴圈邊界。寫入是指對主陣列進行指派，包括未改變的插入鍵。
- 合併排序複製到暫存緩衝區的操作不計入寫入次數。額外記憶體用量也不計入顯示的操作總數。
- 播放速度是為教學目的設定的，並非實際執行時間的效能基準。
在課堂上試試這個實驗
- Q1在此實作中，對於已排序的輸入，為什麼泡沫排序只需要進行 n − 1 次比較？
- Q2陣列長度相同時，對於逆序輸入，哪種演算法的比較次數較少？
- Q3為什麼動畫影格數不是衡量演算法速度的可靠指標？
常見問題
為什麼在插入排序或合併排序過程中，值會短暫重複顯示？
覆寫主陣列時，某個值可能暫存在暫存鍵或合併緩衝區中。視覺化會在每次寫入時顯示主陣列的內容；操作完成後，重複現象就會消失。
合併排序總是寫入次數較少嗎？
不是。合併排序的比較次數成長較有效率，但會反覆將合併結果寫回。操作次數取決於輸入資料，以及具體計算哪些指派操作。