Ch7: Quicksort

本章節要介紹的 Quicksort 是一種非常實用的演算法，也是現今大多數程式語言內建排序函式所採用的演算法。雖然最壞情形是

$\mathrm{\Theta }(n^2)$，但平均來說它的表現非常優異，並且可以原地排序，是許多實際系統中排序的首選。

7-1 Description

• 基本流程：
  • 選定一個 pivot
  • 分成 high side（通常在右邊） 與 low side（通常在左邊）
    • 比 pivot 小的元素放在 low side
    • 比 pivot 大的元素放在 high side
  • 之後在左右遞迴繼續 quicksort
    

7-2 Performance

• 時間複雜度：
  • 最壞情形：
    $\mathrm{\Theta }(n^2)$，發生在每次 pivot 都選到最小或最大元素
  • 平均狀況：
    $\mathrm{\Theta }(n\log n)$
• 空間複雜度：
  $O(1)$，因為是原地排序，空間使用效率高

7-3 A Randomized Version of Quicksort

• 每次呼叫時隨機選取一個當 pivot，能平均分配陣列、避免最壞情況。

7-4 Analysis

• 使用期望值分析法（Expected Value Analysis） 分析執行時間