JavaScriptで配列から重複を削除して並べ替える「ユニークソート」の実装方法

配列から重複する要素を取り除き、同時に並べ替えを行うテクニックは、一般的にユニークソート（一意の並べ替え）と呼ばれます。

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

const arr = [1, 1, 1, 3, 2, 2, 8, 3, 4];

この場合、重複が削除され、昇順に並べ替えられた出力は次のようになります。

const output = [1, 2, 3, 4, 8];

オブジェクトを使ったユニークソートの実装例

ここでは、オブジェクト（連想配列）をマップとして利用し、すでに処理済みの値を記録することで重複を判定する方法を紹介します。

コードは以下の通りです。

const arr = [1, 1, 1, 3, 2, 2, 8, 3, 4];
const uniqSort = (arr = []) => {
    const map = {};
    const res = [];
    for (let i = 0; i < arr.length; i++) {
       if (!map[arr[i]]) {
          map[arr[i]] = true;
          res.push(arr[i]);
       }
    }
    return res.sort((a, b) => a - b);
};
console.log(uniqSort(arr));

処理の流れ

このコードの動作を簡単に解説します。

1. 空のオブジェクト map と、結果を格納する配列 res を用意します。
2. 配列の要素を先頭から順番に走査し、その値が map に存在しない場合のみ、map にフラグを立てて res へ追加します。
3. 最後に sort() メソッドと比較関数 (a, b) => a - b を使って、数値として正しく昇順ソートを行います。

実行結果

コンソールには次のように出力されます。

[ 1, 2, 3, 4, 8 ]

補足：Set を使ったより簡潔な方法

ES2015以降では、Set オブジェクトを利用すると、同じ処理をさらに簡潔に書くことができます。

const uniqSort = (arr = []) =>
  [...new Set(arr)].sort((a, b) => a - b);

console.log(uniqSort([1, 1, 1, 3, 2, 2, 8, 3, 4]));
// [ 1, 2, 3, 4, 8 ]

Set は自動的に重複のない値のコレクションを作成するため、スプレッド構文 [...] で展開して配列に戻し、そのままソートするだけでユニークソートが完成します。どちらの方法でも計算量は O(n log n) 程度となり、実用上十分なパフォーマンスが得られます。