سوال پنجم (از amir.ekhlasi):
- یک الگوریتم مرتب سازی مقایسه ای، الگوریتمی است که در هر مرحله بر حسب صلاح دید الگوریتم دو خانه از یک آرایه را انتخاب می کند و آن دو را با هم مقایسه می کند و در صورت نیاز درایه های آنها را با هم عوض می کند. فرض کنید حسن و حسین دو الگوریتم مرتب سازی مقایسه ای (و تخیلی!) متفاوت طراحی کرده اند. ما آرایه A را به دو الگوریتم می دهیم تا آن را از کوچک به بزرگ مرتب کنند. فرض کنید الگوریتم حسن آرایه A را در n مرحله و الگوریتم حسین آرایه A را در m مرحله مرتب کرده است. ثابت کنید اگر تمام درایه های A متمایز باشند (هیچ دو درایه ای با هم برابر نباشند) زوجیت m و n برابر است.
- یک الگوریتم مرتب سازی مقایسه ای، الگوریتمی است که در هر مرحله بر حسب صلاح دید الگوریتم دو خانه از یک آرایه را انتخاب می کند و آن دو را با هم مقایسه می کند و در صورت نیاز درایه های آنها را با هم عوض می کند. فرض کنید حسن و حسین دو الگوریتم مرتب سازی مقایسه ای (و تخیلی!) متفاوت طراحی کرده اند. ما آرایه A را به دو الگوریتم می دهیم تا آن را از کوچک به بزرگ مرتب کنند. فرض کنید الگوریتم حسن آرایه A را در n مرحله و الگوریتم حسین آرایه A را در m مرحله مرتب کرده است. ثابت کنید اگر تمام درایه های A متمایز باشند (هیچ دو درایه ای با هم برابر نباشند) زوجیت m و n برابر است.
