Erlang の本を読んでいたはずなのに C でクイックソートを書いていた。
- 作者: Joe Armstrong,榊原一矢
- 出版社/メーカー: オーム社
- 発売日: 2008/02/23
- メディア: 単行本(ソフトカバー)
- 購入: 8人 クリック: 284回
- この商品を含むブログ (96件) を見る
qsort([]) -> []; qsort([P|T]) -> qsort([X || X <- T, X < P]) ++ [P] ++ qsort([X || X <- T, X >= P]).
void q_sort(int* a, unsigned int length) { if (length <= 1) {return;} int pivot = a[length-1]; unsigned int iSwap = 0; unsigned int i; for (i = 0; i < length; ++i) { if (a[i] <= pivot) { int tmp = a[i]; a[i] = a[iSwap]; a[iSwap] = tmp; iSwap += 1; } } q_sort(a+iSwap, length-iSwap); q_sort(a, iSwap-1); }
Erlang の本を読んでいて、"Hello, World!!" とか FizzBuzz と同じような扱いのチュートリアルとして、クイックソートはいい題材だなーと思った今日この頃*1。
動作確認担当(“Hello!!”)、ループと条件分岐担当(FizzBuzz)があったら、残るは再帰だよね。再帰するには関数(無名関数とかも含めて)が必要なのもチュートリアルとして高ポイントじゃね?
で、『クイックソート』でググると、なんか妙に行数と使う変数の多いコードばっかり出てきてやっぱりダメなのかもしれない、とも思った。もっと、あってるのか間違ってるのかがハッキリわかって*2、書くのも簡単な再帰を使う処理ってなんだろう。階乗じゃ簡単すぎるというかループで十分だし、ハノイの塔よりはクイックソートの方がまだ簡単な気がするし。うーん。