中央値を求める | Programming Place Plus C言語編 逆引き

トップページC言語編逆引き

このページの概要

以下は目次です。

目的

要素が数値の配列があるとき、その中央値(メジアン)を求めたいとします。

中央値とは、データを小さい順(大きい順)に並べたときに、中央に来る値のことです。データの個数が偶数個の場合には中央には2つの値がありますが、この場合はその2つの平均値を使います参考リンク 1 参照)。

配列から、中央値を求める get_median関数を作ることを考えます。引数に、配列(を指すポインタ)と要素数を指定すると、戻り値で中央値を返します。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array1[] = {4, 2, 6, 9, 2};
    int array2[] = {4, 2, 6, 9, 2, 6};

    printf("%d\n", get_median(array1, SIZE_OF_ARRAY(array1)));
    printf("%d\n", get_median(array2, SIZE_OF_ARRAY(array2)));
}

array1 を昇順に並べ替えると {2, 2, 4, 6, 9} となりますから、array1 の中央値は 4 です。

array2 の方は {2, 2, 4, 6, 6, 9} となります。中央には 4 と 6 があるので、その平均値である 5 が、array2 の中央値です。

SIZE_OF_ARRAYマクロは、配列の要素数を取得するものです。詳細は「逆引き 配列の要素数を求める」を参照してください。

方法①(ソートして中央を調べる)

標準で用意された方法はありませんから、素直に実装します。

配列をいったんソートして、中央にあたる位置にある値を調べます。要素数が偶数個なら、2つの要素の値の平均を取らなければならないことを忘れないようにしましょう。

当然ながら、配列がソート済みになっていることが分かっているのなら、ソート処理は不要です。

配列をソートする方法については、「逆引き 配列をソートする」で扱っているので、詳細は省略します。

配列のソートを、get_median関数の中でやるのか、呼び出し元でソート済みにしておくのかという問題はあります。

どんな状態の配列を渡しても、中央値を返してくれる方が便利なのは間違いないですが、勝手に配列がソートされてしまうのは恐らく問題になります。

int main(void)
{
    int array1[] = {4, 2, 6, 9, 2};

    // ソートされていない配列を渡し、中央値を得る
    int median = get_median(array1, SIZE_OF_ARRAY(array1));

    // ここに帰ってきたとき、array1 の内容は、
    // {2, 2, 4, 6, 9} に変わっている。これは許せるのか?
}

get_median関数の内部で、配列のコピーを作って、コピーの方をソートすれば、array1 に影響を与えずに目的を達成することはできます。しかし、その場合はコピーの処理が加わるので、処理速度は低下するでしょう。

なお悪いことに、C言語でこれを実現するにはメモリの動的割り当てが必要ですし、その解放もきちんと行わなければなりません。処理速度の低下は割と大きなものになるかもしれません。

ここでは、get_median関数内で配列のコピーを作る方法で実装してみます。配列のコピーをつくる方法は「逆引き 配列をコピーする」で取り上げています。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    中央値を求める

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        中央値
*/
int get_median(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size > 0);

    // array のコピーを作って、ソートする
    int* array_copy = malloc(sizeof(int) * size);
    memcpy(array_copy, array, sizeof(int) * size);
    qsort(array_copy, size, sizeof(int), compare_int);

    int median;

    if (size % 2 == 0) {
        // 要素数が偶数個の場合は、中央の要素が2つあるので、その平均値が中央値
        median = (array_copy[size / 2 - 1] + array_copy[size / 2]) / 2;
    }
    else {
        // 要素数が奇数個の場合は、中央の要素の値が中央値
        median = array_copy[size / 2];
    }

    free(array_copy);

    return median;
}

int main(void)
{
    int array1[] = {4, 2, 6, 9, 2};
    int array2[] = {4, 2, 6, 9, 2, 6};

    printf("%d\n", get_median(array1, SIZE_OF_ARRAY(array1)));
    printf("%d\n", get_median(array2, SIZE_OF_ARRAY(array2)));
}

実行結果:

4
5

ソート済みの配列さえ得られれば、あとは比較的素直に実装できます。

配列全体の要素数(仮引数 size)が分かっているので、これが奇数か偶数かを調べて処理を切り分けています。

奇数個の場合は、size / 2 とすれば中央の位置が割り出せます。奇数なので 2 で割ると必ず端数が出ますが、C言語の仕様では切り捨てになるのと(第3章)、配列の添字は 0 から始まるので、中央の位置をあらわす添字が正しく得られます。

偶数個の場合は、size / 2 で得られるのは、中央に来る2つの要素のうち、末尾に近いほうの要素の添字です(array2 の size は 6 なので、中央に来る2つの要素の添字は 2 と 3 です)。なので、これに加えて size / 2 - 1 の位置にある要素の値も取得して、2つの値の平均値を中央値とします。

動的にメモリ割り当てしているため、最後に free関数を呼び忘れないようにしてください。


参考リンク

  1. 中央値 | Wikipedia


更新履歴

’2019/10/7 新規作成。



逆引きのトップページへ

C言語編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る