زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۹:۳۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت

ارسال:
  

shamim1395 پرسیده:

روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت

اگر رویه ی فراخوانی مرتب سازی سریع به صورت بازگشتی این چنین باشد
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]

خیلی ممنون
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Saman پاسخ داده:

RE: روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت

سلام

نمیدونم از چه کتابی خوندید اما چیزی که دارید میگید در رابطه با حالات مختلفی از الگوریتم پارتیشن هست
زمانی که با ارایه های مختلفی از این دست که در مثالتون آوردید الگوریتم ها رو تریس کنید دقیقا این حالات رو متوجه میشوید.
مثلا در پارتیشن (البته حالات مختلفی ازش وجود داره)
با فرض اینکه عنصر اول رو عنصر محوری قرار دهیم :

وقتی ارایه دارای اعداد برابر یا مرتب باشه، شما در هر اجرا از الگوریتم پارتیشن هیچ عنصری رو به طرف دیگه ای از عنصر محوریتون منتقل نمیکنید، حالا همین هیچ رو خانه هایی خالی در نظر بگیرید که به سمت دیگری از عنصر محوری انتقال پیدا میکنند.

یک عنصر که عنصر محوری است، n-1 تا که عناصری هستند که عملیات روشون انجام میشه و هیچ تا خانه هم که به صمت دیگر عنصر محوری میروند.
مجموع این ها + تعداد مقایسه هایی که با عنصور محوری انجام میدید (که n-1) هست تکلیف رابطه بازگشتی مرتب سازی رو روشن میکنه که میشه این :

[tex]T(n)=P(n)+P(0)+n-1[/tex]
شما اینو حل کن به نتیجه مطلوبتون میرسید.

حالا تمام حالات مختلف این نوع از مرتب سازی بر میگرده به شیوه انتخاب عنصر محوری شما.

چند سوال از ۶۰۰ مساله هستن که در این زمینه به شدت پیشنهاد می شوند.البته به گمانم در کتابای کنکوری هم باشن. جایی که آرایه ای رو به صورت رادیکالی با ترکیب insertion و مرتب سازی سریع حل میکنه
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درخواست تصحیح (تعویق) زمان کنکور ارشد ۱۴۰۱ s.gg ۱ ۱۵ ۲۳ بهمن ۱۴۰۱ ۰۷:۴۳ ب.ظ
آخرین ارسال: HamidReza1
  استفاده از پشته armiii ۰ ۱,۱۲۵ ۰۳ دى ۱۴۰۰ ۱۲:۴۳ ق.ظ
آخرین ارسال: armiii
  تعویق زمان کنکور ارشد sima84 ۰ ۱,۷۳۵ ۱۸ اردیبهشت ۱۴۰۰ ۰۱:۰۵ ب.ظ
آخرین ارسال: sima84
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۷۷ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۹۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۴۵ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۷۶۶ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  عمق درخت ???? rad.bahar ۱ ۲,۴۳۰ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۲۴۵ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  کسب درآمد از طریق ارزهای دیجیتال بدون سرمایه alem1 ۰ ۳,۲۹۰ ۱۰ فروردین ۱۳۹۹ ۱۰:۲۶ ق.ظ
آخرین ارسال: alem1

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close