سوال ۳

می‌دانیم مشکل اصلی ‎$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$‎ به‌وجود می‌آید؟ جواب خود را در صورت لزوم با مثال و رابطه‌بازگشتی و یا اثبات بیان کنید.

• سوال بعد
• سوال قبل