コードを書くときに考えること

自分がコードを書くときに考えることとかを書いてみる。例題はクイックソート。

まず、関数の引数を考える。

void quicksort(int array[], size_t n)
{
}

次に関数の中身。とりあえず再帰の終了条件を書いておく。

void quicksort(int array[], size_t n)
{
    if (n <= 1)
        return;
}

クイックソートは、配列をある値より小さい要素の配列と大きい要素の配列の二つに分けることでソートを行うアルゴリズムなんだけど、その二つの配列に分ける作業がわりと難しい。この方法は何種類かあって、例えば次のようなものがある。

後ろに向かうiと前に向かうjとで不確定領域(基準より大きいのか小さいのかわからない領域)を挟み撃ちする感じ。

この方法を使う場合は基準となる要素を配列の頭に持っていかないといけないので、まず0番目の要素と基準となる要素をswapする。

void quicksort(int array[], size_t n)
{
    if (n <= 1)
        return;

    swap(array[0], array[n/2]);
}

ただし、swapは次のようなマクロ

#define swap(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)

次にループを書く。

まず問題はループの継続条件。i < j か i <= j のどちらかっぽいけど、すぐにはわからないので考えてみる。i < jとした場合、ループから抜けたときは i == j な状態になってる。ところが、図を見るとiやjが指している要素の大小はまだ分かっていない。よって i < j だと、ひとつ要素が未確定な状態でループを抜けてしまうことになる。これではだめなので、継続条件は i <= j。

次にループの内側。目標は、図の条件を満たしたままiを++するか、jを--すること。とりあえず、iの指す要素と0番目の要素(基準要素)との大小で分岐がいるだろうなぁと予測。

・array[i] < array[0] の場合は、iをそのまま増やせば図の条件を満たす。
・array[i] >= array[0] の場合は、i番目とj番目の要素を入れ替えれば、jを減らしても図の条件を満たす。

とりあえずこれで書けそうなので書いてみる。

void quicksort(int array[], size_t n)
{
    int i, j;

    if (n <= 1)
        return;

    swap(array[0], array[n/2]);
    for (i = 0, j = n-1; i <= j; ) {
        if (array[i] < array[0]) {
            ++i;
        } else {
            swap(array[i], array[j]);
            --j;
        }
    }
}

もうほとんど完成で、あとは基準の要素を「真ん中」に持ってきて、その他の要素をquicksortすればいい。

まず、「真ん中」が具体的にどこかを考える。ループを抜けた瞬間、iとjは次のようになっている。

0番目の要素は < の方に属するべきだから、j番目の要素とswapすればいい。

void quicksort(int array[], size_t n)
{
    int i, j;

    if (n <= 1)
        return;

    swap(array[0], array[n/2]);
    for (i = 0, j = n-1; i <= j; ) {
        if (array[i] < array[0]) {
            ++i;
        } else {
            swap(array[i], array[j]);
            --j;
        }
    }
    swap(array[0], array[j]);
}

あとは、区間[0, i)と[i+1, n)をquicksortすれば終了。

void quicksort(int array[], size_t n)
{
    int i, j;

    if (n <= 1)
        return;

    swap(array[0], array[n/2]);
    for (i = 0, j = n-1; i <= j; ) {
        if (array[i] < array[0]) {
            ++i;
        } else {
            swap(array[i], array[j]);
            --j;
        }
    }
    swap(array[0], array[j]);
    quicksort(array, j);
    quicksort(array+i, n-i);
}

コンパイルして実行してみる。（main関数は適当に書く）

% gcc qsort.c -o qsort
% ./qsort
Segmentation Fault (core dumped)

落ちた。

このようなプログラムなら、たいていの場合、落ちる原因は配列の範囲外を参照したことなので、範囲外を参照してそうなところを探す。

まず、ループの内側。iは++しかしておらず、初期値は0なので i >= 0。jは--しかしておらず、初期値はn-1なので j <= n-1。ループ中は i <= j なので、0 <= i <= j <= n-1 が成り立つので、配列の範囲外にはでない。

では、ループの外を疑ってみる。ループを抜けたときのiとjの関係は j = i-1 なので、iの変域は 0 <= i <= j+1 = n。一方、jの変域は -1 = i-1 <= j <= n-1。なんかやばそう。j = -1とか確実に落ちる。

よく見るとループのはじめに i = 0 としているのがダウトだ。i = 0は基準の要素を置くところなので、本当はi = 1から始めないといけない。こうすればループを抜けた後では 1 <= i <= n, 0 <= j <= n-1 となる。i = n となる場合が大丈夫なことはループ後のiの使われ方を追跡すると分かる。

i = 0をi = 1になおして、もう一度コンパイルして実行してみる。

void quicksort(int array[], size_t n)
{
    int i, j;

    if (n <= 1)
        return;

    swap(array[0], array[n/2]);
    for (i = 1, j = n-1; i <= j; ) {
        if (array[i] < array[0]) {
            ++i;
        } else {
            swap(array[i], array[j]);
            --j;
        }
    }
    swap(array[0], array[j]);
    quicksort(array, j);
    quicksort(array+i, n-i);
}

% gcc qsort.c -o qsort
% ./qsort
0 1 2 3 4 4 8 9 10

動いた。めでたしめでたし。

昔は、元のコードをちょっとずつ変えていって、試行錯誤しながらコードを書いていたけど、最近は不変条件とか変数の変域とかを考えながら一気に書くことが増えた。そのほうが早いし、バグも減る。