اگر رویه ی فراخوانی مرتب سازی سریع به صورت بازگشتی این چنین باشد
if (Low>High)
return
else
}
partition (A,Low,pivot point)
Quick Sort (A,Low,pivotpoint-1)
Partition(A,Pivot Point+1,high)
{
می دانیم در حالت کلی مرتب سازی سریع از آرایه ی اصلی برای مرتب سازی عناصر استفاده می کند، اما چون یک الگوریتم بازگشتی است و در هر فراخوانی باید دو اندیس در پشته ذخیره شوند، بنابراین در بدترین حالت همواره یکی از زیر لیست های ایجاد شده ( در صورت داشتن آرایه ای صعودی یا نزولی ) تهی است، و دیگری n-1 عنصر خواهد داشت که در این صورت الگوریتم باید n-1 بار به صورت بازگشتی فراخوانی کند، بنابراین عمق پشته بازگشتی از مرتبه n خواهد بود و الگوریتم به فضای کمکی [tex]\theta(n)[/tex] نیاز خواهد داشت
برای بهبود بخشیدن به این فضای مصرفی می توان در هر مرحله زیر لیست کوچکتر را زودتر فراخوانی کرد. در این حالت عمق پشته کمترین شد را خوهد داشت و بیشترین عمق زمانی رخ می دهد که در هر بار لیست ورودی به دو نیمه تقسیم شود که در این حالت عمق پشته و در نتیجه فضای اضاغی مور نیاز [tex]\theta(nlogn)[/tex] خواهد بود
اگر در هر فراخوانی الگوریتم مرتب سازی سریع زیر لیست کوچکتر زودتر به الگروریتم داده شود آنگاه در حالتی که همواره یکی از لیست ها تهی است و دیگری شامل n-1 عنصر عمثق پشته از مرتبه [tex]\theta(1)[/tex] می باشد
می شه این پشته را کمی بیشتر توضیح بدین یا حالا با یک مثالی که با فراخوانی لیست بزرگتر می شود [tex]\theta(n)[/tex] و با فراخوانی لیست کوچکتر می شود [tex]\theta(1)[/tex]
خیلی ممنون
سلام
نمیدونم از چه کتابی خوندید اما چیزی که دارید میگید در رابطه با حالات مختلفی از الگوریتم پارتیشن هست
زمانی که با ارایه های مختلفی از این دست که در مثالتون آوردید الگوریتم ها رو تریس کنید دقیقا این حالات رو متوجه میشوید.
مثلا در پارتیشن (البته حالات مختلفی ازش وجود داره)
با فرض اینکه عنصر اول رو عنصر محوری قرار دهیم :
وقتی ارایه دارای اعداد برابر یا مرتب باشه، شما در هر اجرا از الگوریتم پارتیشن هیچ عنصری رو به طرف دیگه ای از عنصر محوریتون منتقل نمیکنید، حالا همین هیچ رو خانه هایی خالی در نظر بگیرید که به سمت دیگری از عنصر محوری انتقال پیدا میکنند.
یک عنصر که عنصر محوری است، n-1 تا که عناصری هستند که عملیات روشون انجام میشه و هیچ تا خانه هم که به صمت دیگر عنصر محوری میروند.
مجموع این ها + تعداد مقایسه هایی که با عنصور محوری انجام میدید (که n-1) هست تکلیف رابطه بازگشتی مرتب سازی رو روشن میکنه که میشه این :
[tex]T(n)=P(n)+P(0)+n-1[/tex]
شما اینو حل کن به نتیجه مطلوبتون میرسید.
حالا تمام حالات مختلف این نوع از مرتب سازی بر میگرده به شیوه انتخاب عنصر محوری شما.
چند سوال از ۶۰۰ مساله هستن که در این زمینه به شدت پیشنهاد می شوند.البته به گمانم در کتابای کنکوری هم باشن. جایی که آرایه ای رو به صورت رادیکالی با ترکیب insertion و مرتب سازی سریع حل میکنه