درست نیست. در صورت بر زدن الگوریتم مرتب‌سازی درجی از مرتبه‌ی تتای n^2 خواهد بود.

اگر قبل از اجرای الگوریتم عناصر آرایه رو به صورت تصادفی با هم جابجا کنیم بطوریکه احتمال وقوع هر جایگشتی از این اعداد یکسان باشه اونوقت به این کار میگن randomized کردن الگوریتم. این کار یه جورایی میشه همون بر زدن.

تشکر
خیلی لطف کردید

یعنی در بهترین حالت هم دیگه از تتای n نیست؟ میتونه تتای n باشه درست میگم؟
به احتمال [tex]\frac{1}{n!}[/tex]

(۱۸ دى ۱۳۹۲ ۱۲:۲۶ ق.ظ)mahmood1 نوشته شده توسط:  یعنی در بهترین حالت هم دیگه از تتای n نیست؟ میتونه تتای n باشه درست میگم؟

مرتب‌سازی درجی در بهترین حالت از مرتبه‌ی تتای n و در بدترین حالت از مرتبه‌ی تتای n^2 هستش.

عمل بر زدن تاثیری تو درستی جمله‌ی بالا نداره. جمله‌ی بالا در شرایط کلی همیشه درسته.