maxmin  n個のデータから最大値および最小値を求める

void maxmin(int *max, int *min, DATA *data, int nmem);

typedef struct {
    int key;        /* 比較のキーとなるフィールド */
    int info;       /* その他のフィールド */
} DATA;

max   （出力）キーの値が最大のレコード配列の番号（先頭番号は 0）
min   （出力）キーの値が最小のレコード配列の番号（先頭番号は 0）
data  （入力）レコード配列
nmem  （入力）レコード配列の大きさ

なし

void maxmin(int *max, int *min, DATA *data, int nmem)
{
    static void rmaxmin();

    if (nmem <= 0) *max = *min = 0;
    else rmaxmin(max, min, data, 0, nmem - 1);
}

static void rmaxmin(int *max, int *min, DATA *data, int i, int j)
{
    int k;
    int max1, max2, min1, min2;

    if (i+1 >= j) {
        if (data[i].key > data[j].key) {
            *max = i;
            *min = j;
        } else {
            *max = j;
            *min = i;
        }
    } else {
        k = (i + j) / 2;
        rmaxmin(&max1, &min1, data, i, k);
        rmaxmin(&max2, &min2, data, k+1, j);
        *max = (data[max1].key > data[max2].key) ? max1 : max2;
        *min = (data[min1].key < data[min2].key) ? min1 : min2;
    }
}

一方、プログラムのように、n 個のデータを半分ずつに分け、その各々 のグループより最大最小を見つけたとすると、全体の最大値は2つの 最大の大きいほう、全体の最小値は2つの最小の小さいほうである。この 操作を再帰的に各グループの要素が2つになるまで行う。この場合、比較 回数は 3/2n - 2 であり、上記の単純比較法のそれよりも小さい。

利用するには、データ構造を実際の問題に合わせて修正する必要がある。