トランプを使ってマージソートを理解する。

これまでアルゴリズムに強くなりたいと思いながら、有名どころは二分探索、バブルソートくらいしか書けなかった。
そこで、マージソートにチャレンジしようと思ったのだがなかなかうまくいかず、今日ようやく動くものができた。

まぁネットで探せばマージソートのコードなんていくらでも転がっているけど、やはり答えを見るんじゃなくて、どうしても自分で考えてコーディングしたかった。そうすることがスキルアップになるような気がしたので。

さて、マージソートとは、配列を半分、そのまた半分、そのまた半分と切り分けていって、これ以上分けられないところまで来たら、小さい順あるいは大きい順にまとめていくやり方だ。

マージソートの「マージ」とは簡単にいえば、「複数のものを一つにまとめる」ことである。
分けて分けて分けて、これ以上分けられなくなったら、マージしてマージしてマージするソートがマージソート。

今回はトランプカードを使ってマージソートの方法を紹介したい。
人間にとっては非効率に思えるかもしれないが、コンピューターにやらせるには割と効率の良いやり方である。

まず適当にトランプカード8枚をピックアップする。

数字が見えるようにずらしてあるが、上から重なり順と考えて欲しい。
最初は「2, J, 4, Q, 6, 4, K, A」の順に並んでいる。

これを半分にわける。

さらに半分に。

このあと1枚になるまで分けるのだが、まあのこり2枚だし、分かれているものとしよう。
机のスペースの関係でこれ以上はキビシイ。

次に、隣り合ったカード(1枚vs1枚)をマージする。
このとき、小さいものから順にピックアップする。

すると並びは「2, J, 4, Q, 4, 6, A, K」となる。

次にまた、隣り合ったグループ(2枚vs2枚)をマージする。
このときに着目するのは、グループ内のカードはすでにソート済みなので、単純に各グループの先頭からピックアップすれば良いという点。

例えば「2, J」vs 「4, Q」のマージでは、

先頭の2と、同じく先頭の4を比較して2をピックアップ。
残りは「J」vs「4, 9」。

先頭のJと、同じく先頭の4を比較して4をピックアップ。
残りは「J」vs「Q」

先頭のJと、同じく先頭のQを比較してJをピックアップ。
最後に残ったJをピックアップして、「2, 4, J, Q」の並びができる。

全体の並びは「2, 4, J, Q, A, 4, 6, K」となる。

さらに同じルールで隣り合ったグループ(4枚vs4枚)をマージする。
この時もグループ内はすでにソート済みなので、先頭同士の比較で済むことに着目したい。

人間ならパッと小さい数を見つけてその順に拾っていけばソートが完了するが、いざコンピューターにやらせようと思ったら単純なルールにしておかないとプログラム化が難しい。だから先頭同士の比較であることが重要なのだ。

今回使ったのはUSプレイングカード社の紙製トランプ(BICYCLE)

BICYCLE(バイスクル) 808 ライダーバック STANDARD トランプ 赤 ポーカーサイズ

余談だけど、トランプはプラスチックより紙製のほうが本格的なカードらしい。
当然、紙製のほうが安いのだが。
紙とは言ってもコーティングされてかなり弾力もあるのでシャッフルなどもやりやすい。

カジノなどで使用されているのも紙タイプ。(これじゃないけど)
イカサマ防止で定期的にカードを交換するため、破棄しやすい紙製なのだとどこかで読んだ気がするけど、そもそもプラスチックだとインクの張力でカードが反ってしまうらしい。

それで絵札と数字カードとの違いがバレてしまう可能性があるので、お金をかけた真剣勝負にプラスチック製のカードは使えないんだとか。

【情報ソース】
umi-cafe2.at.webry.info

さて、余談が長くなってしまった。
次回は実際にVBAでのマージソートのコードを紹介したいと思う。