مسابقه شماره ۲۰۴
سوال)
یک ردیف از عددهای 1 تا 10 به ما داده شده است. دو عمل زیر را می‌توانیم بر روی هر ردیف انجام دهیم :
-عنصر اول و دوم ردیف را جابجا کنیم.
-عنصر اول ردیف را برداشته , آن را در آخر ردیف قرار دهیم.
آیا با استفاده از دو عمل فوق , می‌توانیم ردیف داده شده را مرتب کنیم؟
پاسخ)
با الگوریتم زیر می‌توان جای هر دو عضو دلخواه مانند i و j با فرض اینکه i قبل از j باشد را عوض کرد :
-ابتدا با توجه به عمل دوم تمام اعضای قبل از i را به انتهای دنباله به ترتیب انتقال می‌دهیم.
-با توجه به عمل اول جای i و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن را به انتهای دنباله انتقال می‌دهیم و این کار را تا جایی ادامه می‌دهیم که i و j مجاور باشند , در این مرحله خود i را به انتها منتقل می‌کنیم.
-با توجه به عمل اول جای j و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن را به انتهای دنباله انتقال می‌دهیم و کار را تا جایی ادامه می‌دهیم که جای خالی i و j پر شود.
-با توجه به عمل دوم تا جای ممکن اعضا را به انتها انتقال می‌دهیم تا ترتیب اولی ظاهر شود با این تفاوت که جای i و j عوض شده باشد.
با الگوریتم بالا ابتدا 1 را به ابتدا , سپس 2 را به جایگاه دوم و ... انتقال می‌دهیم