申論題

5.

(c) [5 points] The following enhanced _quicksort algorithm witten in a C-like pseudo-code tries to first split the array A into three partitions and then recursively sorts the arrays s, M, and L. Note that we carefully design two selection functions, first selection function(A)and second selection function (A), to guarantee that min (A) ＜ x ＜y ＜max (A), where min (A) and max (A) denote the minimum element and the maximum element in array A, respectively. Moreover, we assume that the running time of each selection functions is O(n). Please tell us whether the enhanced quicksort algorithm is more efficient than the quicksort algorithm? Use the big-O notation to justify your answer.