申論題

6. (3 points) A randomized quick sort works as follows. For ease of discussion we assur me that the sequence we want to sort, K = (k₁,... .,k_n), is a pernutution of 1 to n. We randomly and uniformly pick a key & from K. Then we partition K into two subsets - Ki that has keys less than k and K₁ that has keys greater than k. Then we recursively sort K₁and K₂, and combine the results with k to get the sorted sequence.
 1. The number of key comparisons will always be max aunized when the keys in K are already sorted.
 2. Let |K₁| and|K₂|be the number of keys in K₁ and K₂ respectively. The expected value of max(|K₁|,|K₂|) is n.
3. The algorithm will compare two keys &: and ky at most ouce, so the numnber of key comparisons is O(n²). 4. The probability that the algorithm will compare ky and ly (n2i＞ jZ 1) is 
5. Let P= {(i,j)|1≤i，,j ≤ni≠j}. The expected total number of key comparisons is