C++でカウントソートを使って中央値と最頻値を求める方法

サイズnの配列が与えられたとき、カウントソートの手法を応用して中央値（メジアン）と最頻値（モード）を求めることを考えます。この手法は、配列の要素が限られた範囲内にある場合に特に有効です。例えば、要素が{1, 1, 1, 2, 7, 1}である配列の場合、最頻値は1、中央値は1.5となります。

中央値と最頻値とは

• 中央値（メジアン）：数値を昇順に並べたリストの中央に位置する値
• 最頻値（モード）：リスト内で最も多く出現する要素

求め方の手順

中央値と最頻値を求めるには、以下の手順に従います。

1. 入力配列のサイズをnと仮定します。
2. 各値の出現回数を記録するカウント配列を作成します。
3. カウント配列の中で最大値が格納されているインデックスが、与えられたデータの最頻値となります。
4. 最大出現回数の要素が複数存在する場合は、そのうちのいずれかを採用できます。
5. その値をmodeという別の変数に保存します。
6. 続いて、通常のカウントソートの処理に進みます。累積カウントを計算し、ソート済み配列を構築します。
7. ソート済み配列において、nが奇数の場合は中央の要素がそのまま中央値になります。nが偶数の場合は中央の2つの要素を取り出し、その平均値を中央値とします。
8. その値をmedianという別の変数に保存します。

サンプルコード

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 1, 1, 2, 7, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 配列内の最大値を求める
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal)
            maxVal = arr[i];

    // カウント配列を作成して出現回数を記録
    int count[maxVal + 1] = {0};
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // 最頻値を求める
    int mode = 0, maxCount = 0;
    for (int i = 0; i <= maxVal; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            mode = i;
        }
    }

    // カウントソート：累積カウントを計算
    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];

    // ソート済み配列を構築
    int sorted[n];
    for (int i = n - 1; i >= 0; i--)
        sorted[--count[arr[i]]] = arr[i];

    // 中央値を求める
    double median;
    if (n % 2 == 1)
        median = sorted[n / 2];
    else
        median = (sorted[n / 2 - 1] + sorted[n / 2]) / 2.0;

    cout << "最頻値（モード）: " << mode << endl;
    cout << "中央値（メジアン）: " << median << endl;

    return 0;
}

出力

最頻値（モード）: 1
中央値（メジアン）: 1.5

まとめ

このように、カウントソートの考え方を利用すると、要素の範囲が限定された配列から中央値と最頻値をO(n + k)の時間計算量で効率的に求められます（kは要素の最大値）。さらに、ソート済み配列を明示的に構築しなくても、累積カウント配列から中央値の位置を直接特定できるため、メモリ使用量を抑えた実装も可能です。要素の取りうる値の範囲が小さいデータセットを扱う際には、ぜひこの手法を活用してみてください。