C++で桁の合計に基づいて数値をソートする方法

この記事では、各数値の「桁の合計（各桁の数字を足した値）」に基づいて数値を並べ替える方法を解説します。桁の合計が小さい数値ほど先頭に配置され、合計が大きい数値ほど後ろに配置されます。

ソートの例

例として、次のようなデータを考えてみましょう。

data = {14, 129, 501, 23, 0, 145}

このデータを桁の合計順にソートすると、以下のようになります。

• 0 → 桁の合計は 0
• 14 → 桁の合計は 1 + 4 = 5
• 23 → 桁の合計は 2 + 3 = 5
• 501 → 桁の合計は 5 + 0 + 1 = 6
• 145 → 桁の合計は 1 + 4 + 5 = 10
• 129 → 桁の合計は 1 + 2 + 9 = 12

data = {0, 14, 23, 501, 145, 129}

このような独自のルールでソートを行うには、比較用の関数（コンパレータ）を自作する必要があります。C++ STL の sort() 関数では、第3引数にカスタム比較関数を渡すことで、任意の基準による並べ替えが可能です。

アルゴリズム

比較関数のロジックは次のとおりです。

compare(num1, num2):
Begin
    if sum of digits of num1 < sum of digits of num2, then
        return 1
    return 0
End

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

// 各桁の合計を求める関数
int sumOfDigits(int n){
    int sum = 0;
    while(n){
        sum += n % 10;  // 最後の桁を加算
        n /= 10;        // 桁を一つずらす
    }
    return sum;
}

// カスタム比較関数
int compare(int num1, int num2){
    if(sumOfDigits(num1) < sumOfDigits(num2))
        return 1;   // num1 の桁の合計が小さい場合は true を返す
    return 0;
}

int main(){
    int data[] = {14, 129, 501, 23, 0, 145};
    int n = sizeof(data) / sizeof(data[0]);

    // カスタム比較関数を使ってソート
    sort(data, data + n, compare);

    // 結果の出力
    for(int i = 0; i < n; i++){
        cout << data[i] << " ";
    }
}

実行結果

0 14 23 501 145 129

コードのポイント

sumOfDigits 関数： 引数として受け取った整数の各桁を抽出し、その合計を返します。n % 10 で最後の桁を取り出し、n /= 10 で桁を一つずつ削っていくことで、すべての桁を処理できます。

compare 関数： 2つの数値の桁の合計を比較し、num1 の方が小さい場合に true（1）を返します。STL の sort() は、この比較関数が true を返すペアを優先的に前に配置するため、結果として桁の合計が昇順になるように並べ替えられます。

なお、C++11 以降では比較関数をラムダ式で直接記述することもできます。また、同じ桁の合計を持つ要素（14 と 23 など）の順序については、標準の sort() は安定ソートではないため保証されません。元の順序を維持したい場合は stable_sort() を使用するとよいでしょう。