سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

سلام دوستان.
- در جزوه ساختمان داده پارسه صفحه ۲۳۲ گفته شده است که مرتب سازی Selection از نوع نامتعادل (ناپایدار - unstable) است.
- در کتاب ساختمان داده انتشارات نصیر در صفحات ۶۲۹ و ۶۳۰ گفته شده است که این الگوریتم (مرتب سازی انتخابی) دارای پیاده سازی پایدار نیز هست (با دلایل بسیار قوی این حرف را زده و در ادامه این صفحات از کتاب آمده است).
- دکتر سید جوادی در ویس الگوریتم ۸۸ می فرمایند که اگر یک الگوریتم مرتب سازی حداقل یک پیاده سازی پایدار داشته باشد، آن الگوریتم مرتب سازی پایدار است و ضمنا دقایقی بعد (صدای جلسه نه ۷۴:۳۵) می فرمایند که Selection Sort متعادل نیست.

سوال من این است که بالاخره این الگوریتم پایدار است یا خیر ؟

صفحات کتاب انتشارات نصیر، در ادامه آمده است :

[تصویر: 233252_01.jpg]

فایل‌(های) پیوست شده

ارسال: #۲

۰۸ دى ۱۳۹۲, ۱۰:۲۸ ق.ظ

e.shrm پاسخ داده:

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

(۰۸ دى ۱۳۹۲ ۰۵:۴۷ ق.ظ)Morris نوشته شده توسط: سلام دوستان.
- در جزوه ساختمان داده پارسه صفحه ۲۳۲ گفته شده است که مرتب سازی Selection از نوع نامتعادل (ناپایدار - unstable) است.
- در کتاب ساختمان داده انتشارات نصیر در صفحات ۶۲۹ و ۶۳۰ گفته شده است که این الگوریتم (مرتب سازی انتخابی) دارای پیاده سازی پایدار نیز هست (با دلایل بسیار قوی این حرف را زده و در ادامه این صفحات از کتاب آمده است).
- دکتر سید جوادی در ویس الگوریتم ۸۸ می فرمایند که اگر یک الگوریتم مرتب سازی حداقل یک پیاده سازی پایدار داشته باشد، آن الگوریتم مرتب سازی پایدار است و ضمنا دقایقی بعد (صدای جلسه نه ۷۴:۳۵) می فرمایند که Selection Sort متعادل نیست.

سوال من این است که بالاخره این الگوریتم پایدار است یا خیر ؟

صفحات کتاب انتشارات نصیر، در ادامه آمده است :

سلام

دکتر سید جوادی : " مرتب سازی هایی که با پرش کار میکنند پایدار نیستند ، مانند Selection sort"
منبع : جزوه خودم Big Grin

یه بار خودتون الگوریتم رو اجرا کنید میبینید که جای مساوی ها رو هم عوض میکنه
مثلا برای

$4 , {4}',1$ میشه

$1 , {4}' ,4$

البته در مورد جمله دکتر در مورد پیاده سازی پایدار ، نمیدونم منظورشون از یک پیاده سازی پایدار چی بود. چون اگر اینجوری در نظر بگیریم امکان پیاده سازی همه الگوریتم ها بصورت پایدار وجود داره ، اونم به این صورت که برای عناصر مساوی یک اندیس در نظر بگیریم ، در صورت عدم تساوی عناصر که الگوریتم به صورت عادی عمل میکنه ولی در صورتی که کلید ها مساوی بود اون ها رو بر اساس اندیس مرتب میکنیم که باعث مبشه جای عناصر مساوی عوض نشه و الگوریتم پایدار بمونه.

ارسال: #۳

۰۸ دى ۱۳۹۲, ۱۱:۱۷ ق.ظ

Riemann پاسخ داده:

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

خیلی درگیر این جمله ها نشید، چیزی که همه قبول دارن چی هست همونو بخونید، تا اونجایی که من میدونم selection sort پایدار نیست، ولی اینو بدونی که هر الگوریتمی رو میشه پایدار کرد با اضافه کردن این مورد که علاوه بر مقدار، اندیس اعداد هم باهم مقایسه بشن. در کل این جدول فکر کنم خوب باشه: ولی هیپ سورت فکر کنم بهترین حالتش O n باشه اونم وقتی همه ۱ باشن و یکی ۰ و ما مین هیپ بسازیم.

ارسال: #۴

۰۹ دى ۱۳۹۲, ۰۲:۰۸ ق.ظ

Morris پاسخ داده:

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

تشکر فراوان از هر دوی شما دوستان عزیز.

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	[دانلود] ویس و جزوه ی طراحی الگوریتم سیدجوادی	هاتف	۳۳	۴۶,۳۳۹	۰۴ تیر ۱۴۰۲ ۰۲:۰۳ ب.ظ آخرین ارسال: solmaz58
	مبحث جستجوهای محلی	Elham_tm	۷	۴,۷۴۹	۱۷ اسفند ۱۴۰۰ ۰۵:۴۳ ب.ظ آخرین ارسال: KB2000
	کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟	azam2075	۳	۶,۳۲۶	۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ آخرین ارسال: علیصا
	طراحی ui/ux	kimiya1234	۲	۲,۶۲۲	۲۶ بهمن ۱۳۹۹ ۱۰:۴۲ ب.ظ آخرین ارسال: farsamw
	سلام آیا اینجا کسی رشتش کامپیوتر هست؟	parisa1140	۲	۴,۴۱۷	۱۹ بهمن ۱۳۹۹ ۱۱:۰۶ ب.ظ آخرین ارسال: farsamw
	پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو	Happiness.72	۶	۷,۲۲۹	۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ آخرین ارسال: saqarmoshtaq
	هزینه عشق واقعی چقدر است	aatwo	۵	۶,۲۱۵	۱۳ بهمن ۱۳۹۹ ۱۰:۱۴ ب.ظ آخرین ارسال: ghaderZ
	طراحی یک سیستم عامل (از صفر)	sina4everafter	۱۲	۱۷,۲۰۰	۰۶ بهمن ۱۳۹۹ ۱۲:۵۳ ب.ظ آخرین ارسال: nahalmomen2007@yahoo.com
	طراحی سایت ریسپانسیو	wikidemy1	۰	۱,۹۸۷	۱۳ دى ۱۳۹۹ ۰۴:۰۱ ب.ظ آخرین ارسال: wikidemy1
	طراحی الگوریتم ها	amir.m5560@gmail.com	۰	۱,۸۶۱	۳۰ آذر ۱۳۹۹ ۰۸:۲۴ ب.ظ آخرین ارسال: amir.m5560@gmail.com

سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

RE: سوال از مبحث مرتب سازی درس طراحی الگوریتم (آیا Selection Sort پایدار است ؟)

Can I see some ID?

Feeling left out?

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

Feeling left out?