[Algo] 7.3 A randomized version of quicksort

在分析 quicksort 的 average-case 的時候，我們明白到 pivot 選得好不好會決定整個 quicksort 的 running time。在這邊我們隨機的從 $A[p \ldots r]$ 中挑選一個 element 出來跟 $A[r]$ 做交換，因為 pivot 是隨機亂挑的，我們可以期待，以平均來講 split 會是 well balanced 的。

@{
\proc{Randomized-Partition}(A, p, r)
\li i = \proc{Random}(p, r)
\li \textup{exchange}\;A[r]\;\textup{and}\;A[i]
\li \Return \proc{Partition}(A, p, r)
}@

@{
\proc{Randomized-Quicksort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \proc{Randomized-Partition}(A, p, r)
\li \;\;\;\;\proc{Randomized-Quicksort}(A, p, q - 1)
\li \;\;\;\;\proc{Randomized-Quicksort}(A, q + 1, r)
}@