[Introduction To Algorithms] 第七堂: QuickSort

 QuickSort 雖然很熟了，但重點是在它的分析。


開始講之前，老師講了 merge sort 的變化 (分成三堆)，第二種是分成三堆後用 priority queue 分析的方式排序，第二種感覺比較聰明的做法，但是複雜度反而變差，而這種情況當分成√n 堆時，priority queue 會複雜度會比較低。


Divide and Conquer 若是 master thm 派不上用場，最後都有大絕招，猜，然後建構式歸納。

經過分析，每一次 partition 的複雜度取決於基準邊的選取，如果每次基準邊都選到最大，那複雜度會到θ(n²) 。若是基準邊都挑很平均，那麼複雜度就是 θ(nlgn)。

這是以結果論來看，我們不能夠很武斷的說，就是這樣啊~ 需要證明，用的方法就是把所有的 case 挑出來 (這種分析方式要好好學)。


值得提的是，若是基準邊是以固定比例來分，那複雜度還是θ(nlgn)，跟一開始講的 merge sort 分三段一樣。

分析時先試著用直覺的觀念，考慮好壞交錯的情況，發現好壞交錯和最好的情況複雜度相同。

接下來分析 randomized 的版本，在實務應用中，為了避免 worst case 發生，會用 randomize 的方式打散。














分析 best case 只要分析Ω就好，因為上界已經是θ(nlgn)了。
而此分析講義沒有列出，在習題 ex.7.4-2 當作練習。 (跟 worst case 分析ο類似)

worst case 的分析就很重要，先猜，再證明。

這個證明利用到微積分的拋物線球極值的觀念。






















再來就是分析 running time 了

有兩種分析方式，這個作者用觀察的方式來證明，這樣證明比較簡單，而習題有傳統分析的方式。

首先觀察 Quicksort 的特性
發現時間在於 Partition 中的比對次數。


所以可以假設 running time 等於，所有比對的次數。random variable 就派上用場了。










p.14 ~ p.17 用 indicator variable 估算出比對次數，這種解法要記!!

老師補充了第二種方式的證明。


p.18 ~ p.23


其中 p.20 頁課本直接用歸納證明，但 full-history recurrence 其實有經典的解法(前次項減後次項)

p.24 列出了一般教科書的解法。


















Quicksort 是個很重要的問題，因此有很多種分析方式，熟悉這些事很重要的!!




















接下來就用，