سوال ۷۲ کنکور ارشد علوم کامپیوتر ۱۴۰۳

طراحی الگوریتممتوسطالگوریتم‌های مرتب‌سازی

اهمیت

۰/۵

آرایه $A$ شامل $n$ عنصر مرتب (از اندیس $1$ تا $n$ ) و $k$ عنصر نامرتب (از اندیس $n+1$ تا $n+k$ ) است و $k$ مستقل از $n$ و بسیار کمتر از آن می‌باشد. کدام‌یک از الگوریتم‌های زیر برای مرتب‌سازی این آرایه به کمترین تعداد مقایسه نیاز دارد؟

#insertion-sort#nearly-sorted#comparison-count#adaptive-sorting

Approach