ソートアルゴリズム復習

先週、仕事で特殊なソート処理をする必要があったので、かなり久しぶりにクイックソートを実装したのだけど、
実はそんなことやらなくてもいいことに実装した次の日に気付いた。
よく考えたら、比較関数を引数として受け取るソート関数なんて大抵の言語は最初から持ってるよなあ。
単に関数名が分からなかっただけなんだけど。(PHPのusort)
せっかくなのでusortのソースコードを読んでみた。以下、抜粋。

    if (zend_hash_sort(target_hash, zend_qsort, array_user_compare, 1 TSRMLS_CC) == FAILURE) {
        PHP_ARRAY_CMP_FUNC_RESTORE();
     }

同じくクイックソートらしい。zend_qsortの中も見てみる。

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC\
)
{
    void           *begin_stack[QSORT_STACK_SIZE];
    void           *end_stack[QSORT_STACK_SIZE];
    register char  *begin;
    register char  *end;
    register char  *seg1;
    register char  *seg2;
    register char  *seg2p;
    register int    loop;
    uint            offset;

    begin_stack[0] = (char *) base;
    end_stack[0]   = (char *) base + ((nmemb - 1) * siz);

    for (loop = 0; loop >= 0; --loop) {
        begin = begin_stack[loop];
        end   = end_stack[loop];

        while (begin < end) {
            offset = (end - begin) >> 1;
            _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);

            seg1 = begin + siz;
            seg2 = end;

            while (1) {
                for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
                     seg1 += siz);

                for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
                     seg2 -= siz);

                if (seg1 >= seg2)
                    break;

                _zend_qsort_swap(seg1, seg2, siz);

                seg1 += siz;
                seg2 -= siz;
            }

            _zend_qsort_swap(begin, seg2, siz);

            seg2p = seg2;

            if ((seg2p - begin) <= (end - seg2p)) {
                if ((seg2p + siz) < end) {
                    begin_stack[loop] = seg2p + siz;
                    end_stack[loop++] = end;
                }
                end = seg2p - siz;
            }
            else {
                if ((seg2p - siz) > begin) {
                    begin_stack[loop] = begin;
                    end_stack[loop++] = seg2p - siz;
                }
                begin = seg2p + siz;
            }
        }
    }
}    

やはり再帰は使わず、整列範囲をスタックで管理しているようだ。

で、仕事でソートプログラムを組むようなことはあまりないので、せっかくだからソートアルゴリズムの復習をしてみようと思い、
週末は2, 3年以上前に読んだっきりのアルゴリズム本をひっぱり出してひたすらCでソートアルゴリズムを実装していた。
そして今更だが、この本、実は結構良書だということに気付いた。
珠玉のプログラミングとかを読もうと思ってる人は先にこっちを読んだ方がいいかもしれない。

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)

ああ、そういえば、もうすぐ、Beautiful Code の日本語版が出るそうですね。
原書は前から買おうと思ってたんだけど、日本語版が出るならそっちでいいかなあ。

http://www.oreilly.co.jp/editors/archives/000158.html

執筆陣が豪華すぎw。1章と3章がPDFで公開されているので、興味のある人は読んでみるといいです。
とってもビューティフルなコードが載ってます。