سوال ۴۹
یک ترتیب از عددهای ۱ تا ۱۰ به ما داده شده است.
دو عمل زیر را میتوانیم بر روی هر ترتیب انجام دهیم:
آیا با استفاده از دو عمل فوق، میتوانیم ترتیب داده شده را مرتب کنیم؟
پاسخ
با الگوریتم زیر میتوان جای هر دو عضو دلخواه مانند $i$ و $j$ با فرض این که $i$ قبل از $j$ باشد راعوض کرد:
ابتدا با توجه به عمل دوم تمام اعضای قبل از $i$ را به انتهای دنباله به ترتیب انتقال میدهیم.
با توجه به عمل اول جای $i$ و عضو بعد از آن را عوض کرده و سپس باتوجه به عمل دوم آن را به انتهای دنباله انتقال میدهیم و این کار را تا جایی ادامه میدهیم که $i$ و $j$ مجاور باشند٬ در این مرحله خود $i$ را به انتها منتقل میکنیم.
باتوجه به عمل اول جای $j$ و عضو بعد از آن را عوض کرده و سپس با توجه به عمل دوم آن را به انتهای دنباله انتقال میدهیم و کار را تا جایی ادامه میدهیم که جای خالی $i$ و $j$ پر شود.
باتوجه به عمل دوم تا جای ممکن اعضا را به انتها انتقال میدهیم تا ترتیب اولی ظاهر شود با این تفاوت که جای $i$ و $j$ عوض شده باشد.
با الگوریتم بالا ابتدا ۱ را به ابتدا٬ سپس ۲ را به جایگاه دوم و … انتقال میدهیم.