سلام دوستان
دو تا سوال
۱- برای مرتب سازی درجی اگه برای پیدا کردن جای کلید توی آرایه مرتب شده قبل به جای جستجوی خطی از دودویی استفاده کنیم ، مرتبه بدترین حالت به nlogn کاهش پیدا میکنه؟
۲- راهی برای بهبود الگوریتم انتخابی نیست؟ منظورم دقیقا اینه که اون بخش پیدا کردن min رو بهبود بدیم.
مرتب سازی درجی دودویی: پیدا کردن محل عنصر جدید در بخش مرتب شده به کمک جستجوی دودویی و پس از یافتن محل آن ، همه عناصر مرتب پس از آن یک خانه به سمت راست جابجا می شوند.
در مرتب سازی درجی دودویی، تعداد مقایسه ها برای هر عنصر جدید حداکثر logn است. بنابراین تعداد کل مقایسه ها از مرتبه nlogn است. حال باید توجه داشت که علاوه بر مقایسه های انجام شده، برای هر عنصر جدید باید تمام عناصر پس از آن جابجا شوند که دارای مرتبه n است . پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.
(نوع بهبودیافته درجی الگوریتم مرتب سازی صدفی است.)
در مورد الگوریتم انتخابی ،در هر شرایطی حداکثر n-1 جایجایی صورت میگیرد .
البته در اینترنت که سرچ کنید دو الگوریتم پیشنهاد شده برای بهبود الگوریتم انتخابی ولی انچنان مرتبه رو بهبود ندادند که مطرح بشوند!
(۱۶ بهمن ۱۳۹۲ ۰۲:۴۱ ب.ظ)fulgent نوشته شده توسط: پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.اینو مطمئنید؟ بدترین حالت مگه نمیشه nlogn ?
(۱۶ بهمن ۱۳۹۲ ۰۲:۵۴ ب.ظ)masoud67 نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۲:۴۱ ب.ظ)fulgent نوشته شده توسط: پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.اینو مطمئنید؟ بدترین حالت مگه نمیشه nlogn ?
بله ... تعداد کل مقایسه ها میشه nlogn ولی مرتبه کل الگوریتم همانn^2 می شود. توضیح هم دادم چرا اینطوری میشه:
تعداد کل مقایسه ها از مرتبه nlogn است. حال باید توجه داشت که علاوه بر مقایسه های انجام شده، برای هر عنصر جدید باید تمام عناصر پس از آن جابجا شوند که دارای مرتبه n است . پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.
(۱۶ بهمن ۱۳۹۲ ۰۲:۵۸ ب.ظ)fulgent نوشته شده توسط:تشکر. من حواسم به شیفت نبود. من فقط روی مقایسه فکر کردم(16 بهمن ۱۳۹۲ ۰۲:۵۴ ب.ظ)masoud67 نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۲:۴۱ ب.ظ)fulgent نوشته شده توسط: پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.اینو مطمئنید؟ بدترین حالت مگه نمیشه nlogn ?
بله ... تعداد کل مقایسه ها میشه nlogn ولی مرتبه کل الگوریتم همانn^2 می شود. توضیح هم دادم چرا اینطوری میشه:
تعداد کل مقایسه ها از مرتبه nlogn است. حال باید توجه داشت که علاوه بر مقایسه های انجام شده، برای هر عنصر جدید باید تمام عناصر پس از آن جابجا شوند که دارای مرتبه n است . پس مرتبه ی کل مرتب سازی درجی دودویی در بدترین حالت نسبت به مرتب سازی درجی مستقیم تغییری نمی کند و برابر n^2 می شود.
(۱۶ بهمن ۱۳۹۲ ۰۴:۲۵ ب.ظ)masoud67 نوشته شده توسط: تشکر. من حواسم به شیفت نبود. من فقط روی مقایسه فکر کردمخواهش می کنم
متشکرم دوستان