تالار گفتمان مانشت

سلام!
الگوریتم quicksort
Inplace هست یا خیر؟!
Stable چطور؟!
چرا؟!

این الگوریتم stable نیست، چون اگه به کد partition نگاه کنید میاد و یه و دوتا عنصر که کنار هم نیستن رو با هم تعویض میکنه که این ممکنه stable بودن رو بهم بزنه.

inplace هم هست چون از هیچ جافظه ای اضافه که از مرتبه ورودی باشه استفاده نمیکنه.

(18 آذر 1392 05:56 ب.ظ)hoomanab نوشته شده توسط: [ -> ]سلام!
الگوریتم quicksort
Inplace هست یا خیر؟!
Stable چطور؟!
چرا؟!

can you speak farsi?
الگوریتم مرتب سازی سریع درجا هست چون برای مرتب سازی نیازی به حافظه ای متناسب با آرایه ورودی نداره. مثل مرتب سازی ادغامی نیست که به اندازه آرایه ورودی آرایه کمکی نیاز داشته باشه. حداکثر نیاز مرتب سازی سریع چند تا متغیر بیشتر نیست.

و همچنین پایدار یا متعال نیست. دلیلش هم کافیه یه مثال حل کنی باهاش. منم چند سال پیش به این موضوع شک کردم ولی با یه مثال حل کردن رفع ابهام شد برام.
متعادل بودن یعنی اینکه ترتیب عناصر با مقدار یکسان بعد از مرتب سازی مثل قبل بمونه و تغییر نکنه.
مثلا آرایه [tex]\left \{ 4,3,5_{1},1,5_{2},2,5_{3} \right \}[/tex]
بعد از مرتب سازی بشه
[tex]\left \{1,2,3,4,5_{1},5_{2},5_{3} \right \}[/tex]
همونطور که میبینی بعد از مرتب سازی ترتیب عناصر تکراری ۵ به همون صورت قبلی باقی موندن

Thanks to all of you!
سپاس از همه