توی کتاب ارشد سپاهان گفته :
مرتب سازی سریع یک الگوریتم غیر درجا است . مصرف حافظه کمکی ان به دلیل استفاده از پشته در بدترین حالت O(n) و در بهترین و متوسط O(logn) می باشد .
در پوران 'گفته :
الگوریتم مرتب سازی سریع درجا است .
حالا کدوم درست می گن ؟
۱- درجا یا غیر درجا ؟
۲- اگه غیر درجا هست میشه جمله ارشد سپاهان رو یه توضیح بدین ؟
۳-من ار تعریف غیر درجا اینو می دونم "نیاز به حافظه کمکی متناسب با ورودی داریم ." درست ؟
مرتب سازی سریع درجا است.
زیرا حافظه ی کمکی که میخواد همیشه ثابته و برابر تعداد خانه هایی هست که برای جابجایی دو عنصر لازمه.
تنها mergeSort و BST غیردرجا هستن!
فک کنم سپاهان فک کرده چون مرتیه مکانی سریع متغیره(به خاطره طول عملیات Partion) پس غیردرجاست! که این با مفهوم غیر درجا متفاوته!
(۲۳ دى ۱۳۹۱ ۱۲:۲۹ ب.ظ)ana_12345 نوشته شده توسط: توی کتاب ارشد سپاهان گفته :منظور از حافظه ی درجا اینه که برای محاسبه خروجی مقدار حافظه ی اضافی ثابت باشه و به اندازه ی ورودی بستگی نداشته باشه . ولی اگه شما به روند تابع quick sort نگاه کنید می بینید که حافظه ی اضافی کاملا وابسته به اندازه ی ورودی هست . پس این تابع غیر درجاست.
مرتب سازی سریع یک الگوریتم غیر درجا است . مصرف حافظه کمکی ان به دلیل استفاده از پشته در بدترین حالت O(n) و در بهترین و متوسط O(logn) می باشد .
در پوران 'گفته :
الگوریتم مرتب سازی سریع درجا است .
حالا کدوم درست می گن ؟
۱- درجا یا غیر درجا ؟
۲- اگه غیر درجا هست میشه جمله ارشد سپاهان رو یه توضیح بدین ؟
۳-من ار تعریف غیر درجا اینو می دونم "نیاز به حافظه کمکی متناسب با ورودی داریم ." درست ؟
(۲۳ دى ۱۳۹۱ ۰۸:۵۹ ب.ظ)soada نوشته شده توسط: منظور از حافظه ی درجا اینه که برای محاسبه خروجی مقدار حافظه ی اضافی ثابت باشه و به اندازه ی ورودی بستگی نداشته باشه . ولی اگه شما به روند تابع quick sort نگاه کنید می بینید که حافظه ی اضافی کاملا وابسته به اندازه ی ورودی هست . پس این تابع غیر درجاست.
مرسی که پاسخ دادین اما متوجه نشدم ؟؟؟ چرا ؟
(۲۳ دى ۱۳۹۱ ۰۱:۲۱ ب.ظ)asusx59sr نوشته شده توسط: زیرا حافظه ی کمکی که میخواد همیشه ثابته و برابر تعداد خانه هایی هست که برای جابجایی دو عنصر لازمه.
یعنی حافظه مورد نیاز برای الگوریتم مرتب سازی سریع چه قدر ؟؟؟
(۲۳ دى ۱۳۹۱ ۱۰:۳۹ ب.ظ)ana_12345 نوشته شده توسط: یعنی حافظه مورد نیاز برای الگوریتم مرتب سازی سریع چه قدر ؟؟؟
خب ظاهرا یه خونه کافیه دیگه.
ببین اصلا ربطی نداره شما ۱۰ تا ورودی داری یا ۱۰۰۰۰۰ تا. هر وقتی که نیاز به جابجاییه دو عنصر دارید یک خونه به عنوان temp کافیه. اما در مرتب سازی به روش تقسیم غلبه هرچی ورودی زیاد باشه تعداد حافظه ی مورد نیاز بیشتر میشه. روی کاغذ بکش معلومه