人力シェーカーソート問題 – 2025年東大数学第5問

2025年3月6日2025年3月8日

うんちく – ソートアルゴリズムについて

　本問で取り扱っているシェーカーソートは、ソートアルゴリズムの中で一番単純なバブルソートの改良版です。

　バブルソートはまず上りのオペレーション(T₂),(T₃),…,(T_n-1)を行い、次いで(T₂),(T₃),…,(T_n-2)、(T₂),(T₃),…,(T_n-3)とオペレーションの範囲を縮めながら完全に昇順に並ぶまで繰り返す、というものです。

　なんか間抜けな感じもしますがロジックが単純なので、ソート対象が少ないときは重宝します。ただしソートの手間はソート対象の数 n の2乗のオーダーで増えるので、 n が大きくなると厳しいです。

　シェーカーソートはバブルソートに比べると少しは知恵を絞ったな、と言う感じがしますが、こちらも手間は n² のオーダーで増えます。

　ソートアルゴリズムには他にも選択ソート、クイックソート、マージソートと言ったものがあります。これらの中にはソートの手間が n log n のオーダという、シェーカーソートやバブルソートよりも効率的なものもあります。

　詳しくは以下のページをご覧ください。

　小問2で c_n の漸化式が導出されたので、これから一般項を求めると以下の通りです。

c_n = \sqrt{2}^{n-3} \{ ( \sqrt{2}+1)^{n-1} + ( \sqrt{2}-1)^{n-1} \}

　一方、任意の実数 a に対し

\lim_{n \to \infty} \frac{ a^n}{n!} = 0

が成り立つので

\lim_{n \to \infty} \frac{ c_n}{n!} = 0

です。すなわち、カードの枚数が増えるほど1往復オペレーションでソートできる確率はどんどん小さくなります。

　 $\lim\limits_{n \to \infty} \frac{ a^n}{n!} = 0$ を学校で教えていない場合でも、この性質は収束するかどうかの当たりをつけるのに重宝しますので、覚えておきましょう。

　本問は見たことない設問なので面食らいますが、この手の問題は設問内容に慣れさせるため、小問1は簡単なことが多いです。あの東大後期1998年第3問ですら、小問1は単なるパズルです。楽しく遊べますのでチャレンジしてみてください。

　本問の小問1も、よく考えてみると主張しているところは至極当然なので、手堅く得点しましょう。

　小問2はかなりの難問ですが、オペレーションの性質上一番小さいカードが左にあったらそれはずっと左に居続けるので、ここからカード分布を分離できるのではと発想できれば、漸化式を導出することができるでしょう。

　本稿のようにカードを右側に追加していくという発想のほうが自然な感じがしますが、本稿で示したようにそれはハマります。

　小問1の存在がカード列の左側にフィーチャーすべきだという強いメッセージになっているので、小問1は小問2のヒントになっているというセオリーに忠実に従うようにしましょう。