تعریف مرتب سازی پایدار را می دانم اما یک مثال عینی می خواهم مثلا وقتی می گوییم مرتب سازی ادغامی یک مرتب سازی پایدار یا stable می باشد یعنی چه
چرا گفته می شود اگر مرتب سازی ادغامی به راحتی روی داده هایی که در حافظه های جانبی قرار داشته باشند اجرا می شود و بهترین الگوریتم برای مرتب سازی خارجی است منظور این جمله چه می باشد
سلام. وقت بخیر.
پایداری در مورد ترتیب داده‌های با کلید برابر عنوان میشه. اگه دو عنصر، کلید برابر داشته باشن، اونی که تو آرایه زودتر اومده، باید تو آرایه مرتب هم زودتر بیاد. با توجه به نحوه ادغام دو آرایه مرتب، چون دو آرایه‌ای که ادغام میشن مجاور هستن، اون ترتیب رو میشه حفظ کرد. یعنی اگه دو کلید با مقدار برابر تو دوتا آرایه مجاور دیدیم، اول سمت چپی رو قرار میدیم.
در مورد مرتب‌سازی در حافظه، در نظر بگیرید که حافظه موقتمون محدوده و قراره یه آرایه بزرگی که تو حافظه دائم ذخیره شده رو قصد داریم مرتب کنیم. میدونیم که سرعت خوندن و نوشتن حافظه دائم خیلی کمه و خوندن یه عدد با یه بلوک پشت سر هم زمان برابری داره. پس باید دفعات خوندن از حافظه دائم رو کم کنیم و بلوک، بلوک بخونیم. روشی که الگوریتم مرتب سازی ادغامی داره، با این فرضیات وفق پذیره. هم مرتبه زمانی بهینه (با توجه به مقایسه‌ای بودن) داره و هم میتونه دفعات خوندن از حافظه رو کمینه کنه.
(۲۶ دى ۱۳۹۵ ۰۲:۲۳ ب.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر.
پایداری در مورد ترتیب داده‌های با کلید برابر عنوان میشه. اگه دو عنصر، کلید برابر داشته باشن، اونی که تو آرایه زودتر اومده، باید تو آرایه مرتب هم زودتر بیاد. با توجه به نحوه ادغام دو آرایه مرتب، چون دو آرایه‌ای که ادغام میشن مجاور هستن، اون ترتیب رو میشه حفظ کرد. یعنی اگه دو کلید با مقدار برابر تو دوتا آرایه مجاور دیدیم، اول سمت چپی رو قرار میدیم.
در مورد مرتب‌سازی در حافظه، در نظر بگیرید که حافظه موقتمون محدوده و قراره یه آرایه بزرگی که تو حافظه دائم ذخیره شده رو قصد داریم مرتب کنیم. میدونیم که سرعت خوندن و نوشتن حافظه دائم خیلی کمه و خوندن یه عدد با یه بلوک پشت سر هم زمان برابری داره. پس باید دفعات خوندن از حافظه دائم رو کم کنیم و بلوک، بلوک بخونیم. روشی که الگوریتم مرتب سازی ادغامی داره، با این فرضیات وفق پذیره. هم مرتبه زمانی بهینه (با توجه به مقایسه‌ای بودن) داره و هم میتونه دفعات خوندن از حافظه رو کمینه کنه.
خیلی ممنون تشکر