مرتب‌سازی درغامی

الگوریتم (Inserge-Sort(A که هدف‌ش مرتّب‌سازی آرایه‌ی ‎ $A$ ‎ است، بدین صورت است:

‎ $n$ $\leftarrow$ Length( $A$ ); ‎
‎ $k$ $\leftarrow$ Random( $1$ ‎, ‎ $\lfloor\frac{n}{2}\rfloor$ ); ‎
Insertion-Sort( $A[1..k]$ ); ‎
‎ Inserge-Sort( $A[k+1..n]$ ); ‎
Merge( $A[1..k]‎, ‎A[k+1..n]$ );

که منظور از ‎ $A[x..y]$ ‎، زیرآرایه‌ی شامل ‎ $A[x]$ ‎ تا ‎ $A[y]$ ‎ است و تابع ( $y$ , $x$ )Random یک عدد تصادفی در بازه‌ی ‎ $[x,y]$ ‎ برمی‌گرداند‎. ‎

رابطه‌ی بازگشتی زمان اجرای این الگوریتم را بر حسب ‎ $n$ ‎ نوشته و زمان اجرای متوسّط آن را صریحاً تحلیل کنید.

المپدیا

ابزار کاربر

ابزار سایت

مرتب‌سازی درغامی

ابزار صفحه