سوال ۳

می‌دانیم مشکل اصلی $Quicksort$ در پیدا کردن کلید قسمت Partition است. به‌طوری که اگر کلید عنصر مناسبی باشد دو زیر مسئله ما اندازه‌های برابر (و مساوی $\frac{n}{2}$) خواهند داشت و اگر کلید عنصر مناسبی از آب در نیاید، رابطه بازگشتی ما کُند خواهد بود.

برای حل این مشکل، علی قسمت انتخاب کلید تابع Parition را (که روی زیرآرایه‌ی $n=r-l+1$ ،عنصری $A[l..r]$ اجرا می‌شود)، به صورت زیر می‌نویسد.

• ابتدا ماکزیمم عناصر آرایه را در ${\cal O}(n)$ پیدا کن و آن را $M$ بنام.
• سپس مینیمم عناصر آرایه را در ${\cal O}(n)$ پیدا کن و آن را $m$ بنام.
• برای هر عنصر $A_i$ از $n$ عنصر موجود در آرایه (زیر آرایه)، مقدار $C_i = Max(M-A_i,A_i-m)$ را حساب کن.
• عنصری که $C_i$ آن کم‌تر یا مساوی سایر $C_i$ هاست را $q$ بنام ($\forall_{i=l}^r C_q \le C_i$) و $A[q]$ را عنصر کلید برای Partition قرار بده. یعنی $key \leftarrow A[q]$.

دقت کنید که کل این رویه ۵ مرحله‌ای قرارست جایگزین $key \leftarrow A[random(l..r)]$ بشود.

آیا با این کارِ علی تغییری در بهترین و بدترین زمان اجرای الگوریتم $QuickSort$ به‌وجود می‌آید؟ جواب خود را در صورت لزوم با مثال و رابطه‌بازگشتی و یا اثبات بیان کنید.