C言語で比較回数を最小限に抑えて配列の最大値と最小値を求める方法

整数型の配列が与えられたとき、比較回数をできるだけ少なくして、その配列に含まれる最大要素と最小要素を見つけるのが本記事の目的です。

入力例と出力例

例1

入力

Arr[] = { 1, 2, 4, 5, -3, 91 }

出力

Maximum element : 91
Minimum Element : -3

解説： 比較回数を減らすために、まず最大値・最小値の変数を Arr[0] で初期化します。その後、2番目の要素から順に各値を min および max と比較し、条件に応じて更新していきます。

例2

入力

Arr[] = { 10, 20, 21, 31, 18, 11 }

出力

Maximum element : 31
Minimum Element : 10

解説： こちらも同様に、max と min を Arr[0] で初期化し、2番目以降の要素を順番に比較しながら更新することで、効率的に結果を求められます。

プログラムのアプローチ

• 整数の並んだ配列 Arr[] を受け取ります。
• 関数 getresult(int arr[], int n) は、最小限の比較回数で配列内の最大要素と最小要素を求めます。
• 要素が1つだけの場合は、変数 max と min をどちらも arr[0] で初期化します。
• 要素が複数ある場合は、最初の2つの要素を1回の比較で振り分け、大きい方を max、小さい方を min に設定します。
• for ループを使い、3番目の要素（i = 2）から最後まで走査します。
• 各要素 arr[i] を max と比較し、大きければ max を更新します。max より小さい場合は、さらに min と比較し、小さければ min を更新します。この「else if」の構造により、1要素あたりの比較は最大2回、多くの場合1回で済みます。
• 最後に、max と min に格納された結果を出力します。

サンプルコード

#include <stdio.h>
#include <math.h>

int getresult(int arr[], int n){
    int min = 0, max = 0;

    /* 要素が1つだけの場合は、それをminとmaxの両方として返す */
    if (n == 1) {
        min = max = arr[0];
    }

    /* 要素が複数ある場合は、最初の2つでminとmaxを初期化 */
    if (arr[0] > arr[1]) {
        max = arr[0];
        min = arr[1];
    } else {
        max = arr[1];
        min = arr[0];
    }

    for (int i = 2; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
        else if (arr[i] < min)
            min = arr[i];
    }

    printf(" Minimum element: %d", min);
    printf(" Maximum element: %d", max);
}

/* 上記関数をテストするドライバープログラム */
int main(){
    int arr[] = {200, 191, 112, -11, 330, 60};
    int n = 6;
    getresult(arr, n);
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Minimum element: -11
Maximum element: 330

計算量について

この手法では、単純に各要素を min と max の両方と比較する方法（比較回数：約2(n−2)回）と比べて、比較回数を削減できます。本実装では、要素ごとに最大でも2回、平均的には約1.5回程度の比較で済むため、n個の要素に対する総比較回数は最悪でも 2n − 3 回程度に抑えられます。さらに、要素をペアごとに処理する「トーナメント方式」を採用すれば、比較回数を約 3n/2 回まで減らすことも可能です。