برای مرتب‌سازی، عمل «ابرجابه‌جایی» را چنین تعریف می‌کنیم. در هر ابرجابه‌جایی، یک زیررشتهی دلخواه از دنباله‌ی داده‌شده را معکوس می‌کنیم. برای مثال دنباله‌ی ⟨1,4,3,2,5⟩ با یک ابرجابه‌جایی مرتب می‌‌شود. کافی است زیررشتهی ⟨4,3,2⟩ را معکوس کنیم. ولی برای مرتب‌سازی دنباله‌ی ⟨4,2,3,1⟩ دو ابرجابه‌جایی نیاز داریم. ابتدا کل دنباله را معکوس می‌کنیم تا به ⟨1,3,2,4⟩ برسیم. سپس زیررشتهی ⟨3,2⟩ را معکوس می‌کنیم. حداقل تعداد ابرجابه‌جایی که برای مرتب‌سازی هر دنباله‌ی دلخواه به طول ۴ کافی است، چند است؟
راهنمایی
فرض کنید اعداد 1 تا i در جایگاه درست خود قرار دارند. آیا می‌توان عدد i+1 را در جایگاه درستش قرار داد به طوری که در نهایت، اعداد 1 تا i نیز همچنان در جایگاه درست خود قرار داشته باشند؟
پاسخ
گزینه‌ی ۲ درست است.
با حالت‌گیری و رسیدن به دنباله‌ی ⟨3,1,4,2⟩ جواب به دست می‌آید.