C++で配列内の全要素のランクを求める方法｜総当たり法と効率的なアルゴリズムを解説

この記事では、配列内のすべての要素にランク（順位）を割り当てる問題を扱います。最も小さい数値には最小のランクを、最も大きい数値には最大のランクを付与します。さらに、同じ値が複数回出現する場合は、その出現頻度に応じてランクを調整する必要があります。

問題の例

入力 : 20 30 10
出力 : 2.0 3.0 1.0

入力 : 10 12 15 12 10 25 12
出力 : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0

上記の2つ目の例では、値「10」のランクが「1.5」になっています。これは、配列内に「10」が2つ存在するためです。もし両者が異なるランク（1と2）を取ると仮定すると、その平均を取ることでそれぞれのランクは「1.5」となります。このように、同順位の要素にはランクの平均値が割り当てられます。

入力 : 1, 2, 5, 2, 1, 60, 3
出力 : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

解決策へのアプローチ

この問題を解くには、主に2つのアプローチがあります。

• 総当たり（ブルートフォース）アプローチ
• ソートを活用した効率的なアプローチ

方法1：総当たり（ブルートフォース）アプローチ

この方法では、各要素を選択してループ処理を行い、その要素のランクを直接計算します。具体的には、「自分より小さい要素の数」と「同じ値の要素の出現頻度」をもとに、次の式でランクを求めます。

ランク = （より小さい要素の数）+（同値の要素数 − 1）/ 2 + 1

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 25, 2}; // 対象の配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ

    float rank[n] = {0}; // ランクを格納する配列
    for (int i = 0; i < n; i++) {
        int r = 1; // arr[i] より小さい要素の数
        int s = 1; // arr[i] と等しい要素の数

        for (int j = 0; j < n; j++) {
            if (j != i && arr[j] < arr[i])
                r += 1;

            if (j != i && arr[j] == arr[i])
                s += 1;
        }
        // 式を使って各要素のランクを算出
        rank[i] = r + (float)(s - 1) / (float) 2;
    }

    for (int i = 0; i < n; i++) // ランクを出力
        cout << rank[i] << ' ';

    return 0;
}

実行結果

1.5 4 6 4 1.5 7 4

このプログラムの時間計算量は O(N²) です（Nは配列のサイズ）。ネストしたループ構造のため、配列が大きくなると処理速度が大幅に低下します。そこで、次により効率的なアプローチを見ていきましょう。

方法2：ソートを活用した効率的なアプローチ

この方法では、まず元の配列をコピーし、そのコピーをソートします。ソート済みの配列では、同じ値の要素が必ず隣接して並ぶため、先頭から順にランクを振りながら、同値のグループごとにランクの平均を計算できます。

C++での実装例

#include <bits/stdc++.h>

using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 60, 3}; // 対象の配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    float rank[n] = {0}; // ランクを格納する配列
    int old[n];
    for(int i = 0; i < n; i++)
        old[i] = arr[i]; // 元の順序を保持
    sort(arr, arr+n); // 配列をソート
    int prev = arr[0];
    int r = 1;   // 現在のランク
    int s = 0;   // 出現頻度
    int tot = 0; // ランクの累積合計
    map<int, float> rrank;

    for (int i = 0; i < n; i++) {
        if(prev == arr[i]) {
            s++;      // 同じ値なら頻度を増加
            tot += r; // ランクを累積
        } else {
            float now = 0;
            now = (float)tot/s; // ランクを均等に分配
            rrank[prev] = now;
            prev = arr[i];
            tot = r;
            s = 1;
        }
        r++;
    }
    rrank[arr[n-1]] = (float)tot/s; // 最後のグループを処理
    for (int i = 0; i < n; i++) // ランクを出力
        cout << rrank[old[i]] << " ";

    return 0;
}

実行結果

1.5 3.5 6 3.5 1.5 7 5

コードの解説

このアプローチでは、まず配列をソートし、先頭の要素から順にランク（1から開始）を割り当てていきます。直前の要素（prev）と現在の要素が等しい場合は、出現頻度 s を増やしながらランクの合計 tot に加算していきます。値が変化したタイミングで、それまでに累積したランクを頻度で割って平均値を求め、マップに登録します。その後、カウンターをリセットして次のグループの処理へ進みます。最後に、元の配列の順序に従って各要素のランクを出力することで、正しい結果が得られます。

この方法の時間計算量は O(N log N) であり、ソートのコストが支配的になります。総当たり法の O(N²) と比較して、大規模なデータセットでも高速に動作する点が大きな利点です。

まとめ

本記事では、配列内のすべての要素のランクを求める問題を解説しました。同値の要素にはランクの平均を割り当てるというルールのもと、シンプルな総当たり法と、ソートを活用した効率的な手法の2つのアプローチとC++プログラムを紹介しました。同じロジックは、C、Java、Pythonなど他のプログラミング言語でも同様に実装できます。データサイズが大きい場合は、O(N log N) の効率的なアプローチを採用することをおすすめします。