EmptyPage.jp > Whining Express > 2002-06-19
サイトの更新情報や日々の雑感など。
TX-Cにはテキストを行でソートするtxSortというAPIがあります。この関数、「タブ区切りテキストの何番目のカラムで並べ替え」などが可能な高度なオプションを備えているわりには、数値としてソートができなかったりと、汎用的なソート関数としてはいまいちです。ANSI Cのqsort関数もTX-Cでは使えません。
そこで、練習もかねて汎用クイックソート関数をTX-Cで組んでみました。参考文献はまたまた『定本 Cプログラマのためのアルゴリズムとデータ構造』。あとはWebでいろいろ解説を読んだり。
テキストを行ごとに配列に読み込んでソートさせるテストマクロ（サンプルコードに付属）でベンチマーク（笑）を取ってみたところ、ynp5版xhtml.txc（約304 KB、9845行）のソートに561ミリ秒、W3CのHTML 4.01 Specificationのplain text版（約773 KB、18908行）のソートに1151ミリ秒と実用にも耐えられそうな感じです（ThinkPad X20、320 MB RAM）。さすがTX-C。
素朴に再帰呼び出しをしてたり、ループ内でmalloc/freeを繰り返してたりするので、工夫すればもうちょっと速くなりますかね……。