سلام دوستان.
- در جزوه ساختمان داده پارسه صفحه ۲۳۲ گفته شده است که مرتب سازی Selection از نوع نامتعادل (ناپایدار - unstable) است.
- در کتاب ساختمان داده انتشارات نصیر در صفحات ۶۲۹ و ۶۳۰ گفته شده است که این الگوریتم (مرتب سازی انتخابی) دارای پیاده سازی پایدار نیز هست (با دلایل بسیار قوی این حرف را زده و در ادامه این صفحات از کتاب آمده است).
- دکتر سید جوادی در ویس الگوریتم ۸۸ می فرمایند که اگر یک الگوریتم مرتب سازی حداقل یک پیاده سازی پایدار داشته باشد، آن الگوریتم مرتب سازی پایدار است و ضمنا دقایقی بعد (صدای جلسه نه ۷۴:۳۵) می فرمایند که Selection Sort متعادل نیست.
سوال من این است که بالاخره این الگوریتم پایدار است یا خیر ؟
صفحات کتاب انتشارات نصیر، در ادامه آمده است :
![[تصویر: 233252_01.jpg]](https://img.manesht.ir/233252_01.jpg)
![[تصویر: 233252_02.jpg]](https://img.manesht.ir/233252_02.jpg)
(۰۸ دى ۱۳۹۲ ۰۵:۴۷ ق.ظ)Morris نوشته شده توسط: سلام دوستان.
- در جزوه ساختمان داده پارسه صفحه ۲۳۲ گفته شده است که مرتب سازی Selection از نوع نامتعادل (ناپایدار - unstable) است.
- در کتاب ساختمان داده انتشارات نصیر در صفحات ۶۲۹ و ۶۳۰ گفته شده است که این الگوریتم (مرتب سازی انتخابی) دارای پیاده سازی پایدار نیز هست (با دلایل بسیار قوی این حرف را زده و در ادامه این صفحات از کتاب آمده است).
- دکتر سید جوادی در ویس الگوریتم ۸۸ می فرمایند که اگر یک الگوریتم مرتب سازی حداقل یک پیاده سازی پایدار داشته باشد، آن الگوریتم مرتب سازی پایدار است و ضمنا دقایقی بعد (صدای جلسه نه ۷۴:۳۵) می فرمایند که Selection Sort متعادل نیست.
سوال من این است که بالاخره این الگوریتم پایدار است یا خیر ؟
صفحات کتاب انتشارات نصیر، در ادامه آمده است :
سلام
دکتر سید جوادی : " مرتب سازی هایی که با پرش کار میکنند پایدار نیستند ، مانند Selection sort"
منبع : جزوه خودم
یه بار خودتون الگوریتم رو اجرا کنید میبینید که جای مساوی ها رو هم عوض میکنه
مثلا برای [tex]4 , {4}',1[/tex] میشه [tex]1 , {4}' ,4[/tex]
البته در مورد جمله دکتر در مورد پیاده سازی پایدار ، نمیدونم منظورشون از یک پیاده سازی پایدار چی بود. چون اگر اینجوری در نظر بگیریم امکان پیاده سازی همه الگوریتم ها بصورت پایدار وجود داره ، اونم به این صورت که برای عناصر مساوی یک اندیس در نظر بگیریم ، در صورت عدم تساوی عناصر که الگوریتم به صورت عادی عمل میکنه ولی در صورتی که کلید ها مساوی بود اون ها رو بر اساس اندیس مرتب میکنیم که باعث مبشه جای عناصر مساوی عوض نشه و الگوریتم پایدار بمونه.
خیلی درگیر این جمله ها نشید، چیزی که همه قبول دارن چی هست همونو بخونید، تا اونجایی که من میدونم selection sort پایدار نیست، ولی اینو بدونی که هر الگوریتمی رو میشه پایدار کرد با اضافه کردن این مورد که علاوه بر مقدار، اندیس اعداد هم باهم مقایسه بشن. در کل این جدول فکر کنم خوب باشه: ولی هیپ سورت فکر کنم بهترین حالتش O n باشه اونم وقتی همه ۱ باشن و یکی ۰ و ما مین هیپ بسازیم.
تشکر فراوان از هر دوی شما دوستان عزیز.