چی شد؟ کسی جوابی نداره برای این سوال؟ پیچیدگی زمانی در حالت متوسط برای مرتب سازی درجی رو هم می خام. اگه کسی میتونه لطفا کمک کنه.

من خودم یه چیزایی به ذهنم میرسه ولی نمی تونم کاملش کنم
اگر آرایه مرتب باشه با یک پیمایش از برنامه خارج میشیم پس احتمالش و تعداد اجراش به صورت زیر میشه
$\frac{1}{n!}\longrightarrow(n-1)$
اگر بعد از یک بار پیمایش به یک آرایه مرتب برسیم احتمالش و تعداد اجراش فکر می کنم اینطوری بشه
$\frac{(n-1)+(n-1)(n-2)+...+(n-1) (n-2)...1_{ }}{n!}\longrightarrow(n-1)+(n-2)$
نهایتا همه اینا باید دوتا دوتا در هم ضرب و نتایج جمع بشن. میدونمم احتمالا جوابش باید بشه
$\frac{n(n-1)}{4}$
کسی نمیتونه کمک کنه به یک راه حا صریح و شفاف برسیم؟