主观题：Randomized Quicksort

Let's consider the **Randomized Quicksort** where each pivot is randomly chosen from the subsequence.  The following is the pseudo-code:
```
RandQSort( A, L, R ) {
    if (L < R) {
        i = random(L, R);
        swap(A[i], A[R]);
        p = Partition(A, L, R);
        RandQSort( A, L, p-1 );
        RandQSort( A, p+1, R );
    }
}
```
Show that the **expected** running time is $$O(n\log n)$$ for sorting $$A[1\cdots n]$$.

Hint: `Partition` is called $$n$$ times.  Each call takes a constant time plus the number of comparisons with the pivot.  Hence the total run time is $$O(n+X)$$ where $$X$$ is the total number of comparisons with the pivots.  You need to prove that $$E[X]=O(n\log n)$$.






答案：