Shellsortを『写経』する

お疲れ様です。Y研究員です。K＆Rの制御構造を写経しています。

使っているのはWhileやForなどの基本構文ですが、それでも面白い発見があったので共有します。

まずはShellsort。LinuxのShellと関係あるかと思いきや、１９５９年に考案したのがD.L.Shellさんでした。ちゃんと調べると挿入ソートの一種ながら安定ソートではないと分かりました。（同じ要素があった場合は、最初の順番をキープしない）

/* shellsort: sort v[0]...v[n-1] into increasing order */
void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for (gap = n / 2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)
            {
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
}

ソートは調べてみると、かなりの種類があることがわかります。そしてまだ最新の研究が進められているようです。アルゴリズムは『写経』の題材に最適なネタなので、いろんなソートの『写経』も良いかなと思いました。

次は、文字配列を逆にするreverseでコンマのエグい使い方がありました。

/* reverse: reverse string s in place */
void reverse(char s[])
{
    int c, i, j;
    for (i = 0, j = strlen(s) - 1; i < j; i++, j--)
        c = s[i], s[i] = s[j], s[j] = c;
}

If文やFor文の後が１行だとカッコでくくらなくても良いのですが、コンマを使ってねじ込めるそうです。あまり現代では見ない書き方のような気がします。自分で使わないとは思いますが、勉強になりました。

これで制御構造の章が終わったので、次は関数です。ざっと見たら逆ポーランド記法が出てくるようで面白そうです。

写真はだいぶ前に撮った三浦半島の海岸です。Shellから連想しました。

それではまた！

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

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