好き勝手に・げーあにん?

ファミコンと同い年の社会人ヌルオタの日記

言語のチュートリアルに向いている再帰処理ってなんだろう

Erlang の本を読んでいたはずなのに C でクイックソートを書いていた。

プログラミングErlang

プログラミングErlang

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、書くのも簡単な再帰を使う処理ってなんだろう。階乗じゃ簡単すぎるというかループで十分だし、ハノイの塔よりはクイックソートの方がまだ簡単な気がするし。うーん。

*1:この Erlangクイックソートは効率度外視。わかりやすさ優先のコードとして紹介されています

*2:自分の書いたソートがあってるのか不安すぎる