مرتب سازی درجی دودویی: پیدا کردن محل عنصر جدید در بخش مرتب شده به کمک جستجوی دودویی و پس از یافتن محل آن ، همه عناصر مرتب پس از آن یک خانه به سمت راست جابجا می شوند.
در مرتب سازی درجی دودویی، تعداد مقایسه ها برای هر عنصر جدید حداکثر 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 نوشته شده توسط:  تشکر. من حواسم به شیفت نبود. من فقط روی مقایسه فکر کردم

خواهش می کنم

متشکرم دوستان