『写経』の道から少し外れて道草をした

お疲れ様です。Y研究員です。『写経』でプログラミングを学ぶには、お手本から離れて違うものを作ってみると良いと書きました。今日は、教科書の『写経』は少しお休みして、ソートを深堀してみたいと思います。

先日、Shellsortを写経してから他のソートもあったなと思い、Wikipediaを開いたら４０種類くらいあると分かりました。そこで一番簡単なバブルソートを書いてみました。こういうのが一発で書けると良いですが、境界条件を１つ間違えるバグを仕込んで、配列に入ってない数字が結果に表示されました。幸いプログラムを眺めることでバグを発見できたので、そのまま修正しました。

バブルソート - Wikipedia

K研究員からは「学生時代に俺が考えた最強のソート」を共有してもらいました。Pythonで書いてきたので、Cで書き直してみました。K研究員から教えてもらったので勝手にk-sortと名付けましょう（クラスタリングのk-meansみたいですね）。しかし、最近のマシンは64bitなので、MINからMAXまで全探索すると一つの要素に対して２の６４乗回も比較をしなければなりません。実際に動かしてみると反応が帰ってきません。。。

input = [100, 200, 5, -38, 89]
sorted = []
for i in range(INT_MIN, INT_MAX):
    for j in input:
        if i == j:
            sorted.append(i)

そこで改良型としてky-sortを書いてみました（K研究員のアイディアをY研究員が改良したという意味で）。実装は以下のとおりです。

void ky_sort(int v[], int vr[], int length)
{
    int max, min;
    max = min = v[0];

    for (int i = 0; i < length; i++)
    {
        if (v[i] < min)
            min = v[i];
        else if (v[i] > max)
            max = v[i];
   }

    int k = 0;
    for (int i = min; i <= max; i++)
    {
        for (int j = 0; j < length; j++)
        {
            if (i == v[j])
            {
                vr[k] = i;
                k++;
            }
        }
    }
}

これも結局、配列内要素の値域に依存するアルゴリズムなので、面白いながらあんまり賢くはありません。しかしこれが駄目かと言われると、上には上がいるので、もっと「すごい」アルゴリズムを紹介して今日は締めたいと思います。その名もボゴソート。簡単に書くとランダムに並べ替えて判定し続ければいつかはソートが完了するという、博打的なアルゴリズム？です。バカバカしいように聞こえますが、かなり理論の研究がされている面白いテーマと分かりました。

無限の猿定理 - Wikipedia

さて、今日はC言語の『写経』から脱線しました。しかし、しばらく『写経』をしているとアレコレ作ってみたくなるものです。その興味に任せてやってみると、お手本だけでは分からないことも発見できるので良いと思います。その例示として、もう一回くらいはソートで遊んでみたいと思いました。

写真は大昔のラズパイです。C言語を書いたりコンパイルはSSH接続をしてラズパイからやってます。今見たらRPi4は４GBでも新品価格が１万円を超えていてすごいことになってますね。。。

それではまた！

般若心経の写経とプログラムの『写経』に関する記事はこちらからどうぞ。

効果的なプログラミングの『写経』とは｜KY研究所@CoderDojo横浜港北ニュータウンやってます｜note