3つの変数の中央値を求める。

クイックソートでPivotを決めるときに3つの値の真ん中をPivotにする手法がある。
それで中央値(Median)を求めるための処理を考えたのだが思ったよりややこしい。

最大値を求めるときは簡単だ。

int getMax(int tmpMax, int x, int y)
{
    if (tmpMax < x) {
        tmpMax = x;
    }

    if (tmpMax < y) {
        tmpMax = y;
    }

    return tmpMax;
}

最小値は不等号の向きを逆にするだけである。あ、変数名はtmpMinにすべきだ。

ところが中央値だと最初の直感より難しい。
素直にコーディングするとこうなった。

int getMedian(int x, int y, int z)
{
    if (x < y) {
        if (y < z) {
            /* x < y < z */
            return y;
        } else {
            /* y is max of three */
            return (x < z)? z: x;
        }
    } else {
        if (z < y) {
            /* z < y < x */
            return y;
        } else {
            /* y is min of three */
            return (x < z)? x: z;
        }
    }
    /* never reach */
    assert(0);
}

ぱっと見でこのコードが正しいかどうかわからない。
もうちょっとうまくかけないかと思い次のようなコードを仕立てた。

#define SWAP(type, x, y)    do {type tmp; tmp = x; x = y; y = tmp;} while(0)

/* 3つの引数の中央値を返す */
int getMedian(int tmpMax, int x, int y)
{
    if (tmpMax < x) {
        SWAP(int, tmpMax, x);
    }
    if (tmpMax < y) {
        SWAP(int, tmpMax, y);
    }
    /* x,yのうち大きいほうが中央値 */
    return (x < y) ? y : x;
}

最大値、最小値を求めるときは上書きして気にしない、気にしないなのだが、
このコードでは後で最大の方を捨ててしまう。

とりあえず個人で行き着いたのはこんなコードだ。
これは自分に対する今後の課題にしておく。