تابع ‎$Q(A)$ ‎ (که $A[1..n]$ آرایه‌ای از اعداد غیرتکراری است) یک جایگشت ‎$\pi$‎ از اعداد ‎۱‎ تا ‎$n$‎ را برمی‌گرداند بدین صورت که ‎$\pi_i = b(A[i],A)$‎ که ‎$b(x,A)$‎ برابر است با تعداد اعداد کوچکترمساوی ‎$x$‎ در ‎$A$‎.

تابع ‎$R(\pi,S)$‎ که ‎$\pi$‎ یک جایگشت و ‎$S\subset\{1,\dots,n\}$‎ آرایه‌ی ‎$A[1..n]$‎ را برمی‌گرداند که $A[i]=\pi_i‎ - ‎n$ برای $i \in S$ و $A[i] = \pi_i$ برای $i \notin S$.

‎ می‌خواهیم با اجرای توابع ‎$Q$‎ و ‎$R$‎ بر روی یک جایگشت ‎$\pi$‎ آن را مرتب کنیم. ثابت کنید با ‎$\left\lceil{\log_2(n)}\right\rceil$‎ بار استفاده از ‎$R$‎ می‌توان هر جایگشتی را مرتب کرد.

راهنمایی: وارون جایگشت را در نظر بگیرید.

• سوال بعد
• سوال قبل