JavaScriptで配列を出現頻度の昇順に並べ替える方法

問題

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成する必要があります。配列 arr には重複した要素が含まれている可能性があります。

この関数では、出現回数が少ない要素から順に配列を並べ替えます。つまり、出現頻度の低い要素を先頭に配置し、頻度の昇順に沿って残りの要素を並べていきます。

なお、出現回数が同じ要素が複数存在する場合は、それらを値の昇順（小さい順）に配置する必要があります。

入力例

const arr = [5, 4, 5, 4, 2, 1, 12];

出力例

[1, 2, 12, 4, 4, 5, 5]

出力の解説

数値「1」「2」「12」はそれぞれ1回しか出現しないため、値の昇順に並んでいます。その後ろには、2回ずつ出現する「4」と「5」が続きます。

サンプルコード

以下が実際のコードです。

const arr = [5, 4, 5, 4, 2, 1, 12];
const sortByAppearance = (arr = []) => {
    // まず値の昇順にソートしておく
    arr.sort((a, b) => a - b);
    const res = [];
    const searched = {};

    // 対象の値が出現する回数をカウントする関数
    const countAppearance = (list, target) => {
        searched[target] = true;
        let count = 0;
        let index = list.indexOf(target);
        while(index !== -1){
            count++;
            list.splice(index, 1);
            index = list.indexOf(target);
        };
        return count;
    };

    const map = [];
    arr.forEach(el => {
        if(!searched.hasOwnProperty(el)){
            map.push([el, countAppearance(arr.slice(), el)]);
        };
    });

    // 出現回数の昇順に並べ替え
    map.sort((a, b) => a[1] - b[1]);

    map.forEach(([num, freq]) => {
        while(freq){
            res.push(num);
            freq--;
        }
    });
    return res;
};
console.log(sortByAppearance(arr));

実行結果

[1, 2, 12, 4, 4, 5, 5]

コードの解説

この実装の流れは次のとおりです。

1. まず sort() で配列全体を値の昇順に並べ替えておきます。
2. countAppearance() 関数が、まだ調査していない要素について出現回数をカウントし、[要素, 回数] のペアとして map 配列に格納します。
3. map を出現回数の昇順にソートします。
4. 最後に、各要素を出現回数の分だけ結果配列 res に追加していきます。

元の配列はあらかじめ値の昇順にソートされているため、ユニークな要素は小さい順に map へ登録されます。そのため、出現回数によるソートで同頻度の要素が並んでも、安定ソートによって値の昇順が保たれます。

より効率的な実装例（Mapを使った方法）

上記のコードは indexOf() と splice() を繰り返し呼び出すため、計算量が O(n²) 程度になり、大きな配列では処理速度が低下します。事前に Map オブジェクトで各要素の出現回数をカウントしておけば、よりシンプルかつ高速に実装できます。

const sortByAppearance = (arr = []) => {
    // 各要素の出現回数をカウント
    const countMap = new Map();
    for (const num of arr) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }

    // 頻度の昇順、同一昇順、同一頻度なら値の昇順でソートして返す
    return [...arr].sort((a, b) => {
        const diff = countMap.get(a) - countMap.get(b);
        return diff !== 0 ? diff : a - b;
    });
};

const arr = [5, 4, 5, 4, 2, 1, 12];
console.log(sortByAppearance(arr)); // [1, 2, 12, 4, 4, 5, 5]

この方法では、比較関数の中でまず「出現回数の差」を評価し、差がゼロ（＝同頻度）の場合にのみ値の大小を比較することで、すべての要件を1回のソートで満たせます。計算量は O(n log n) に収まり、コードの可読性も大幅に向上します。

まとめ

本記事では、配列を出現頻度の昇順（同頻度の場合は値の昇順）に並べ替えるJavaScript関数の実装方法を紹介しました。indexOf() ベースの素朴な実装と、Map を活用した効率的な実装の両方を理解しておくと、実際の開発業務やコーディングテストで役立つでしょう。