Algorithms Part 1 - Week 3–4之Quicksort筆記

Free online course presented by Robert Sedgewick and Kevin Wayne

• 20世紀十大演算法之一
• 廣泛運用在各個方面

來一件Quicksort T-shirt也蠻酷的🤣但這件寫得不是很優喔，居然用(left + right) / 2，不怕overflow嗎😂

---

Quicksort基本想法

1. array洗牌
2. 切開array，在index j的左邊都比它小，index j的右邊都比它大
3. 遞迴再sort左邊和右邊subarray

可參考此網站，視覺化演算法

Implementation

細節注意

• extra space可以讓其partition操作更簡單，且stable，但為此犧牲效能不值得
• pointers交叉比想像中的還難測試與判斷
• j == lo是冗餘的判斷，i == hi不是
• Shuffling需要保證其性能以免拖累整個演算法
• When duplicates are present, it is (counter-intuitively) better
  to stop on keys equal to the partitioning item’s key. <-這句我看不懂

Quicksort有多Quick?

還是那句話，好的演算法絕對比超級電腦更加實用

效能重點(其餘請見PPT)

• Worst case最多有$N^2$次比較
• 平均是~$1.39N lg N$次比較，比mergesort快39%因為資料移動比較少次
• 有很多教科書的實作其實是$O(N^2)$，因為
  • array sorted或是反sorted
  • 有太多重複的數

性質

• in-place sorting algorithm
• Not stable，因為資料位置會被移動

實際的improvements

• 很小的subarrays可以換使用insertion sort，因為Quicksort成本太高
• 取中位數當Pivot
• Median-of-3 (random) items -> 我的理解是隨機取樣本的三個Median?會小幅度的減少比較，並需要比較多的移動，不過可以減少10%的執行時間

重複的鍵

當鍵的數量不多時，也就代表會有很多重複的鍵，此時quicksort就不快了，會需要quadratic time，除非在遇到相同key的時候就停止partitioning

原先的quicksort會把相同key都放到同一邊去，這樣如果有很多相同的，就會變成兩邊不平衡從而降低演算法的效率

這個問題是在1990年代時被發現的，那時有人發現C語言的library中qsort()有這個缺陷，解決方法隨即被提出

解決方法-3 way partitioning

• 切成三部分，左邊小於pivot，中間等於，右邊大於

系統預設的演算法

• Java的Arrays.sort()會根據不同的資料型態使用不同演算法，例如遇到primitive types會使用quicksort，遇到物件(reference types)會使用mergesort，因為效率穩定又是stable(也就是排序時不會影響到彼此之間的相對順序)
• PPT中還有更多擴展內容請參閱