JavaScriptで優先度付きソートを実装する方法

本記事では、JavaScriptを使って「優先度付きソート」を実装する方法を解説します。具体的には、2つの数値配列を受け取り、1つ目の配列を昇順に並べ替えながら、2つ目の配列にも含まれている要素をすべて配列の先頭に配置する関数を作成します。

要件の整理

今回実装する関数に求められる仕様は以下のとおりです。

• 2つの数値の配列を受け取る(2つ目の配列は1つ目よりもサイズが小さい)
• 1つ目の配列を昇順にソートする
• ただし、両方の配列に共通して存在する要素は、すべて先頭に移動する

入力例と出力例

たとえば、次のような2つの配列が与えられたとします。

const arr1 = [5, 4, 3, 2, 1];
const arr2 = [2, 3];

この場合、期待される出力は次のようになります。

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

共通要素である「2」と「3」が先頭に配置され、それ以外の要素(1, 4, 5)は昇順に並んでいることが確認できます。

実装コード

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

const arr1 = [5, 4, 3, 2, 1];
const arr2 = [2, 3];

// 比較用ヘルパー関数
const sorter = (a, b, arr) => {
   if(arr.includes(a)){
      return -1;
   };
   if(arr.includes(b)){
      return 1;
   };
   return a - b;
};

// 優先度ソート本体
const prioritySort = (arr1, arr2) => {
   arr1.sort((a, b) => sorter(a, b, arr2));
};

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

コードの解説

この実装のポイントは、Array.prototype.sort() に渡す比較関数の設計にあります。

• sorter 関数:引数として受け取った要素 a または b が、優先配列(arr2)に含まれているかどうかを includes() で判定します。a が含まれていれば -1(a を手前へ)、b が含まれていれば 1(b を手前へ)を返します。どちらも含まれていない場合は、通常の数値比較である a - b を返すため、残りの要素は自然に昇順へ並べられます。
• prioritySort 関数:arr1 を sort() で並べ替える際に、上記の sorter を比較関数として渡すことで、「優先要素は先頭へ・その他は昇順」という並び順を一度のソートで実現しています。

パフォーマンスに関する補足

includes() は呼び出しごとに線形探索(O(n))を行うため、配列が大きくなると処理速度に影響が出る可能性があります。大量のデータを扱う場合は、あらかじめ Set に変換しておくと効率的です。

const set = new Set(arr2);
arr1.sort((a, b) => {
   if(set.has(a)) return -1;
   if(set.has(b)) return 1;
   return a - b;
});

Set.has() は平均的に O(1) で動作するため、大規模データでも高速に判定できます。

出力結果

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

[ 2, 3, 1, 4, 5 ]