: 推 LPH66: 所以一個常見的方法其實是先把 pivot 放在陣列"開頭" 04/09 07:17
: → LPH66: 接著用你的方法維護成 [pv][<pv ... <pv][>pv ... >pv] 04/09 07:18
: → LPH66: 最後再用你這一步想做的交換把 [pv] 擺在兩塊中間 04/09 07:18
: → LPH66: 概念上其實和你已經寫好的差不多, 只是不是另起變數存 pv 04/09 07:19
: → LPH66: 重點在於這一步既然要是陣列元素對換, 那就把 pv 也擺進去 04/09 07:20
: → LPH66: 定位問題就先找個好定位的地方放就好 (例如陣列開頭) 04/09 07:21
: 感謝回答，其實我原本寫的就是把pivot放最後的，這樣交換不會有問題沒錯，但就是想
: 試試看把pivot放中間，有沒有方法可以追蹤pivot最後換到的位子呢?
: ※ 編輯: nasty1122 (101.9.7.42), 04/09/2019 15:09:44
相信你可能看過一種設計演算法的邏輯叫做「迴圈不變量 (loop invariant)」
它的概念是, 在一個迴圈裡我們會對一個資料結構進行更新
更新的過程可能會更動資料結構的組合
但是在迴圈的開始和結束時我們會要求資料結構具有某個性質
更新當中時破壞掉無所謂, 只要一圈動作作完時這個性質有回來就好
這個性質稱做這個迴圈的「迴圈不變量」
(叫「量」可能會以為只是某個數值, 但其實它是可以指任何我們想要的性質的)
這種設計的好處在於, 有一個明確的性質可以幫助迴圈內容的設計
而且這個性質也能夠在迴圈結束時證明這個迴圈確實做好了某些事
(本版一篇久遠之前的文章也有簡單談了 loop invariant: #13r5O_TK (C_and_CPP)
====
上面引的這篇老文提到說通常, 這個不變量就是我們迴圈結束之後想要的結果
回到 quick sort 來看
這裡的迴圈不變量是 [pv][<pv ... <pv][>pv ... >pv] 這樣的內容排列
每一次迴圈就是加入下一個陣列元素, 然後把它排成符合這個不變量的排列
這樣就能知道為什麼迴圈中是寫成
if (下一元素 < pivot) 交換此元素和分界點元素;
====
那麼現在你想要的是把這個不變量改成 [<pv ... <pv][pv][>pv ... >pv] 這樣的排列
這樣我們可以思考一下加入元素時要怎麼保持這個不變量
> pivot 時和前一種做法一樣什麼事都不用做
< pivot 時, 我們會需要把 >pv 區的第一個元素搬到後面, pv 後移, 再把新元素放進去
┌┐┌─────┐
│↓│ ↓
[<pv ... <pv][pv][>pv ... >pv][new]
↑ │
└───────┘
如果將 pv 所在索引值記錄在 pvidx 的話, 寫起來大概會像這樣:
if (arr[i] < arr[pvidx])
{
int temp = arr[i];
arr[i] = arr[pvidx+1];
arr[pvidx+1] = arr[pvidx];
arr[pvidx] = temp;
++pvidx;
}
====
可以看到, 同樣是分邊的想法, 不變量設定的方式不一樣寫出來的迴圈也就不一樣
因此也就有一種改進迴圈的方式是設法找到更好的不變量條件來用
繼續以 quick sort 為例, 同樣是分邊
原本保持 pv 在中間的做法有三次的移動元素
但 pv 一開始我們就拿著不用每次搬, 所以如果把不變量簡化成 pv 位置留空:
[<pv ... <pv][ ][>pv ... >pv]
每一圈的移動就只剩下兩次
然後再考慮到 pv 原本也是陣列元素之一, 所以放回去比另外存更好
因此把不變量的兩半排在一起, pv 找個不會被碰到的位置放回陣列裡
就變成了這種不變量: [pv][<pv ... <pv][>pv ... >pv]
兩次的移動也合併成了一個交換了, 這就是你所看到過的常見 quick sort 實作