2002-06-19

TX-Cにはテキストを行でソートするtxSortというAPIがあります。この関数、「タブ区切りテキストの何番目のカラムで並べ替え」などが可能な高度なオプションを備えているわりには、数値としてソートができなかったりと、汎用的なソート関数としてはいまいちです。ANSI Cのqsort関数もTX-Cでは使えません。

そこで、練習もかねて汎用クイックソート関数をTX-Cで組んでみました。参考文献はまたまた『定本 Cプログラマのためのアルゴリズムとデータ構造』。あとはWebでいろいろ解説を読んだり。

テキストを行ごとに配列に読み込んでソートさせるテストマクロ(サンプルコードに付属)でベンチマーク(笑)を取ってみたところ、ynp5版xhtml.txc(約304 KB、9845行)のソートに561ミリ秒、W3CHTML 4.01 Specificationのplain text版(約773 KB、18908行)のソートに1151ミリ秒と実用にも耐えられそうな感じです(ThinkPad X20、320 MB RAM)。さすがTX-C。

素朴に再帰呼び出しをしてたり、ループ内でmalloc/freeを繰り返してたりするので、工夫すればもうちょっと速くなりますかね……。