====== سوال ۴۹ ======

یک ترتیب از عددهای ‎۱‎ تا ‎۱۰‎ به ما داده شده است. 
دو عمل زیر را می‌توانیم بر روی هر ترتیب انجام دهیم:
  * عنصر اول و دوم ترتیب را جابه‌جا کنیم.
  * عنصر اول ترتیب را برداشته، آن را در آخر ترتیب قرار دهیم.

آیا با استفاده از دو عمل فوق، می‌توانیم ترتیب داده شده را مرتب کنیم؟
<پاسخ>


با الگوریتم زیر می‌توان جای هر دو عضو دلخواه مانند $i$ و $j$ با فرض این که $i$ قبل از $j$ باشد راعوض کرد:

  * ابتدا با توجه به عمل دوم تمام اعضای قبل از $i$ را به انتهای دنباله به ترتیب انتقال می‌دهیم.
  * با توجه به عمل اول جای $i$ و عضو بعد از آن را عوض کرده و سپس باتوجه به عمل دوم آن‌ ‌را به انتهای دنباله انتقال می‌دهیم و این کار را تا جایی ادامه می‌دهیم که $i$ و $j$ مجاور باشند٬ در این مرحله خود $i$ را به انتها منتقل می‌کنیم.
  * باتوجه به عمل اول جای $j$ و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن‌ را به انتهای دنباله انتقال می‌دهیم و کار را تا جایی ادامه می‌دهیم که جای خالی $i$ و $j$ پر شود.
  * باتوجه به عمل دوم تا جای ممکن اعضا را به انتها انتقال می‌دهیم تا ترتیب اولی ظاهر شود با این تفاوت که جای $i$ و $j$ عوض شده باشد.

با الگوریتم بالا ابتدا ۱ را به ابتدا٬ سپس ۲ را به جایگاه دوم و ... انتقال می‌دهیم.

</پاسخ>
  * [[سوال ۵۰|سوال بعد]]
  * [[سوال ۴۸|سوال قبل]]