(۲۷ دى ۱۳۹۱ ۰۲:۱۷ ق.ظ)csharpisatechnology نوشته شده توسط:  حالت متوسط الگوریتم مرتب سازی انتخابی میشه n
نکته: در حالت متوسط مرتب سازی انتخابی از مرتب سازی سریع بهتر هست.

مرتبه مرتب‌سازی انتخابی در هر سه حالت بهترین، متوسط و بدترین میشه بیگ اوی n^2
در نتیجه هر دو جمله بالا غلط هستن

بذارید به طور واضح یه جمع بندی بکنم.

از الگوریتم selection به طور کلی برای یافتن kامین بزرگترین (یا کوچکترین) عنصر یک آرایه استفاده می‌شه. این الگوریتم رو با مرتب‌سازی انتخابی (Selection Sort) اشتباه نگیرید. برای مسئله selection الگوریتمی وجود داره که در بهترین، بدترین و حالت متوسط دارای مرتبه بیگ اوی n هستش. این یعنی اون چیزی که تو پوران نوشته درسته. توضیح این الگوریتم هم تو فصل ۹ CLRS اومده.

نه
در بهترین و متوسط O(N)
در بدترین O(n^2)

(۲۶ دى ۱۳۹۱ ۰۱:۵۴ ق.ظ)adel28 نوشته شده توسط:  در پاسخ تشریحی پارسه گفته که از الگوریتم Selection استفاده می کنیم.

منظور الگوریتم Selection هست نه مرتب‌سازی انتخابی (selection sort). این دوتا کاملا به هم متفاوت هستن

[/quote]
منظور الگوریتم Selection هست نه مرتب‌سازی انتخابی (selection sort). این دوتا کاملا به هم متفاوت هستن
[/quote]

فکر کنم اشتباه من هم همین هست.
میشه در مورد الگوریتم Selection یکم توضیح بدید.
مربوط به کدوم بحث هست؟

فصل ۹ ویراست سوم CLRS

متوسط O_N
بدترین : O_N^2

---

حالت متوسط الگوریتم مرتب سازی انتخابی میشه n
--
نکته : مرتب سازی سریع در حالت متوسط میشد :nLogN
--
نکته: در حالت متوسط مرتب سازی انتخابی از مرتب سازی سریع بهتر هست.

---

فایل پیوست رو دانلود کن

سلام. توی کتاب ساختمان داده پوران یه اثباتی نوشته شده که من متوجهش نشدم. فکر کنم نوشته بود میشه با پیچیدگی خطی، i امین کوچکترین عنصر در آرایه رو پیدا کنیم. تا اونجایی که یادمه آرایه رو مرتب نمیکرد. از اثباتش چیزی نفهمیدم برای همین بیخیالش شدم.

بچه ها بالاخره چی شد؟الگوریتم selection در بدترین و بهترین حالت توی کتاب پوران نوشته o(n) هست ...متوسطش هم n هست یا n به توان۲ ؟؟

توی selection داریم :
بهترین و متوسط میشه o_n
بدترین میشه n^2
-----
توی quick sort داریم:
متوسط : NlogN
بدترین : n^2
----
نکته ی دیگه : مرتب سازی انتخابی در حالت متوسط از مرتب سازی سریع بهتره.

دوستان حق با mfXpert هست.
الگوریتم انتخابی (Selection) با مرتب سازی انتخابی (Selection) متفاوت هست.
اشتباه من هم همین بود که این دو رو یکی در نظر می گرفتم.