JavaScriptで要素の出現頻度に基づいて配列を並べ替える方法

概要

本記事では、リテラルの配列を第一引数(唯一の引数)として受け取るJavaScript関数を作成します。対象となる配列には同じ値が繰り返し含まれている可能性があり、作成する関数は出現頻度が低い値ほど前へ、出現頻度が高い値ほど後ろへ配置するように配列を並べ替えるものです。

要件の確認

たとえば、入力配列が次のような場合を考えてみましょう。

const arr = [4, 7, 3, 5, 5, 4, 7, 9, 2, 1, 5, 7, 5, 5, 9];

このとき、期待される出力配列は以下のとおりです。

const output = [
    3, 2, 1, 9, 9, 4,
    4, 7, 7, 7, 5, 5,
    5, 5, 5
];

結果を見ると、「3」「2」「1」といった1回しか出現しない値が先頭に配置され、最も多く出現する「5」(5回)が末尾に来ています。また、出現回数が同じ値同士(「3・2・1」や「9・4」など)については、値が大きい方が先に並ぶ仕様になっている点にも注目してください。

サンプルコード

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

const arr = [4, 7, 3, 5, 5, 4, 7, 9, 2, 1, 5, 7, 5, 5, 9];
const sortByNumbers = (arr = []) => {
    const map = {};
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        map[arr[i]] = map[arr[i]] || [0];
        map[arr[i]][0]++;
        map[arr[i]][1] = arr[i];
    }
    const sorted = Object.values(map).sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0]
    });
    for (let i = 0; i < sorted.length; i++) {
        const [freq, num] = sorted[i]
        for (let j = 0; j < freq; j++) {
            res.push(num);
        }
    }
    return res;
};
console.log(sortByNumbers(arr));

コードの解説

このコードの処理は、大きく次の3つのステップで構成されています。

1. 出現回数の集計： まずオブジェクト map を用意し、配列を走査しながら各値ごとに出現回数(インデックス0)と値そのもの(インデックス1)を記録していきます。
2. ソート処理： Object.values() で集計結果を配列として取り出し、出現回数の昇順にソートします。出現回数が同一の場合は b[1] - a[1] の比較により、値の降順で並ぶように制御しています。
3. 結果配列の構築： 最後にソート済みのデータを順番に走査し、各値を出現回数の分だけ結果配列 res へ追加していきます。

計算量としては、要素の集計にO(n)、ソートにO(k log k)(kはユニークな値の種類数)かかるため、全体として効率的な処理となっています。

実行結果

上記コードを実行すると、コンソールには次のように出力されます。

[
    3, 2, 1, 9, 9, 4,
    4, 7, 7, 7, 5, 5,
    5, 5, 5
]

期待どおり、出現回数が少ない値から順に並び替えられていることが確認できます。