مرتب ساز

تعداد نا به جایی‌های جایگشت $\pi= \langle \pi _1, \pi_2, …,\pi_n \rangle$ به طول $n$ برابر تعداد اندیس‌های $i$ و $j$ است که $i \lt j$ و $\pi_i \gt \pi_j$. برای مثال تعداد نابه جایی‌های جایگشت $ \langle1,3,4,2 \rangle $ برابر ۲ و تعداد نا به جایی‌های جایگشت $ \langle3,2,4,1 \rangle$ برابر ۴ است. تعداد نابه جایی‌های جایگشت $\pi$ را با $f(\pi)$ نشان می‌دهیم.

۱۰۰ کارت داریم که پشت هر کارت یکی از اعداد ۱ تا ۱۰۰ نوشته شده است. به بیان دیگر اعداد نوشته شده پشت کارت ها تشکیل یک جایگشت می‌دهند. هم چنین یک ماشین با ۱۰۰ جایگاه مخصوص کارت با شماره‌های ۱ تا ۱۰۰ در اختیار داریم. کارت ها را با ترتیب دلخواه در این ۱۰۰ جایگاه طوری قرار می‌دهیم که در هر جایگاه دقیقا یک کارت قرار گیرد. کارت ها طوری قرار داده شده اند که عدد نوشته شده پشت آن ها را نمی بینیم. دقت کنید که هر وضعیت قرار گرفتن کارت ها در ماشین مشخص کننده‌ی یک جایگشت $\pi$ است. جایگشت $\pi$ به این صورت مشخص می‌شود که عدد نوشته شده بر روی کارت موجود در جایگاه $i$ ماشین نشان دهنده‌ی $\pi_ i$ است. وضعیت ایده آل وضعیتی است که کارت با عدد $i$ در جایگاه به شماره $i$ قرار گیرد. هدف رسیدن به وضعیت ایده آل است. برای رسیدن به این هدف می‌توان در هر مرحله به صورت زیر عمل کرد:

• دو عدد $i$ و $j$ را به ماشین می‌دهیم. فرض کنید وضعیت فعلی ماشین مشخص کننده‌ی جایگشت $\pi$ است. ماشین کارت‌های موجود در جایگاه $i$ و $j$ را با هم جابه جا می‌کند. فرض کنید وضعیت ماشین در حالت جدید مشخص کننده‌ی جایگشت $\acute{\pi}$ است. ماشین علاوه بر جابه جایی کارت‌های موجود در جایگاه $i$ و $j$ مقدار $f(\acute{ \pi})- f (\pi)$ را نیز در خروجی نشان می‌دهد.

روشی ارائه دهید که برای هرگونه وضعیت اولیه قرار گرفتن کارت ها در ماشین، آن ها را در ۱۹۸ مرحله به وضعیت ایده آل تبدیل کند.