勉強会お疲れ様でした。
ながせさんが基礎で、えぴさんが応用で、私がひねくれ者と、
三者三様でかぶらないところが素敵でした。
さて、シェアソートの基本的な所は、Wikipediaによる解説や
前回のエントリーのマクロを動かしてもらうとして、書ききれなかった所を書いていきます。
数字が複雑に動くので、何回やったらソートが終わるのか不安になりますが、
これは明確に回数が求められます。
最悪パターンを見ながらその仕組みを説明します。
このように、1行に収まるべきデータが縦になっている状態が最悪パターンで、
最もソート完了まで時間がかかる状態です。
なお、青色の要素は最後に先頭行に、橙色の要素は最後に末尾行に来る要素です。
緑はちょうど真ん中の行に来る要素です。
まずは、横ソートを行います。
最上段の要素と最下段の要素が左右に二分されました。
上記のデータに縦ソートを行いました。
青、橙の高さが半分になっています。
さらに横ソート→縦ソートを行いました。
青、橙の要素は6→3と半分になっています。
さらに横ソート→縦ソートを行いました。
段々と一行にまとまっていこうとしています。
このように、横ソート→縦ソートのセットで高さが半分になっていくのです。
さらに横ソート→縦ソートを行うと、すべての要素で行が合うようになりました。
このあと、横ソートを行って仕上げを行います。
このように、高さが1になるまでソートを繰り返せばよく、
一度横ソート→縦ソートを行うと高さが半分になるため、
一辺の長さを何回2で割れば1以下となるか、という問題に帰着します。
今回の場合は、11×11なので、一辺の長さは11です。
11は8<11<16のため、4回割ってやれば1になります。
横ソート→縦ソートのセットが4回と、最後の仕上げの横ソートをくわえ、
121個の要素の場合は、9回ソートを行えば完了することになります。
これを数学的に書くと、
という式ができあがります。
何回2で割れば1以下になるか、というのを表現する部分がややこしくなってますね。