مرتب سازی

ثابت کنید که هر الگوریتم مرتب‌سازی که مبتنی بر مقایسه باشد و فقط مجاز باشد که جای دو عدد مجاور در رشته را با هم تعویض کند از مرتبه‌ی زمانی $\Omega(n^2)$ است.

پاسخ