JavaScriptで相対的な順序に基づいて配列をソートする方法

この記事では、JavaScriptを使って「相対的な並べ替え（Relative Sort）」を実装する方法を解説します。

問題の概要

2つの配列、たとえば arr1 と arr2 があるとします。arr2 の要素はすべて重複がなく、かつ arr2 のすべての要素は arr1 にも含まれています。

ここで求められるのは、次のような処理を行うJavaScript関数の実装です。

• arr1 の要素を、arr2 における要素の相対的な順序と同じ順序になるようにソートする。
• arr2 に存在しない要素は、arr1 の末尾に昇順で配置する。

入力例

const arr1 = [2,3,1,3,2,4,6,7,9,2,19];
const arr2 = [2,1,4,3,9,6];

期待される出力

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

出力を見ると、arr2 の順序（2 → 1 → 4 → 3 → 9 → 6）に従って arr1 の該当要素が並び、arr2 に含まれない 7 と 19 は末尾に昇順で配置されていることがわかります。

実装コード

この問題は、Mapオブジェクトを活用することで効率的に解決できます。まず arr2 の各要素とそのインデックスをMapに登録し、その情報をもとにカスタム比較関数で arr1 をソートします。

const arr1 = [2,3,1,3,2,4,6,7,9,2,19];
const arr2 = [2,1,4,3,9,6];

const relativeSortArray = (arr1, arr2) => {
  const map = new Map();
  const len = arr2.length;

  // arr2の各要素とそのインデックスをMapに登録
  arr2.forEach((a, i) => {
    map.set(a, i);
  });

  return arr1.sort((a, b) => {
    // arr2に含まれる要素はそのインデックスを優先度として使う
    // 含まれない要素は len + a として大きい値を与え、末尾に回す
    a = map.has(a) ? map.get(a) : len + a;
    b = map.has(b) ? map.get(b) : len + b;
    return a - b;
  });
};

console.log(relativeSortArray(arr1, arr2));

コードの解説

このアルゴリズムのポイントは以下の通りです。

1. Mapによる順序の記録： arr2 の各要素をキーとして、その出現位置（インデックス）をMapに保存します。これにより、各要素の「優先度」をO(1)で参照できるようになります。
2. カスタム比較関数： sort() の比較関数内で、両方の要素が arr2 に含まれる場合はMapから取得したインデックス同士を比較します。これにより、arr2 の相対的な順序が保たれます。
3. 未登録要素の処理： arr2 に存在しない要素には len + a（len は arr2 の長さ）という値を与えます。これは必ず arr2 のどのインデックスよりも大きいため、自動的に末尾へ回されます。また、元の数値自体が比較に使われるため、同じく未登録の要素同士は昇順に並びます。

実行結果

コンソールの出力は以下のようになります。

[
  2, 2, 2, 1, 4,
  3, 3, 9, 6, 7,
  19
]

計算量について

Mapへの登録にO(M)（Mは arr2 の長さ）、ソートにO(N log N)（Nは arr1 の長さ）かかるため、全体の時間計算量は O(N log N) です。空間計算量はMapの分だけ余分に必要となり、O(M) となります。

まとめ

Mapを使って要素の順序情報を管理し、Array.prototype.sort() のカスタム比較関数と組み合わせることで、相対的な並べ替えを簡潔かつ効率的に実装できます。arr2 に含まれない要素の扱い（len + a という工夫）もポイントです。同様のパターンは、他のカスタムソートの課題にも応用できます。