JavaScriptで実装する特殊なソートアルゴリズム ― 偶数は昇順・奇数は降順に並べ替える

問題の概要

整数の配列を唯一の引数として受け取るJavaScript関数を作成します。この関数は、次の条件に従って配列を並べ替える必要があります。

• すべての偶数は昇順（小さい順）に並べる

• すべての奇数は降順（大きい順）に並べる

• 偶数と奇数の相対的な位置関係は元のまま維持する

入力例

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

const arr = [12, 17, 15, 24, 1, 6];

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

const output = [6, 17, 15, 12, 1, 24];

偶数（12, 24, 6）を昇順に並べると「6, 12, 24」、奇数（17, 15, 1）を降順に並べると「17, 15, 1」になります。これらの値が、それぞれ元の配列で偶数・奇数が占めていた位置へそのまま収まるため、位置関係も崩れません。

実装例

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

const arr = [12, 17, 15, 24, 1, 6];
const specialSort = (nums = []) => {
   const oddArr = [], evenArr = [];
   for (let i = 0; i < nums.length; i++){
      if (nums[i] & 1) {
         oddArr.push(i);
      } else {
         evenArr.push(i);
      }
   }
   nums.sort((a, b) => a - b);
   let odd = oddArr.length - 1, even = 0;
   const res = [];
   for (let i = 0; i < nums.length; i++){
      if (nums[i] & 1) {
         res[oddArr[odd--]] = nums[i];
      } else {
         res[evenArr[even++]] = nums[i];
      }
   }
   return res;
}

アルゴリズムの解説

この実装のポイントは、値そのものではなく「偶数・奇数がどのインデックスに存在するか」を先に記録しておく点にあります。処理の流れは以下のとおりです。

1. 最初のループで配列を走査し、奇数があるインデックスを oddArr へ、偶数があるインデックスを evenArr へそれぞれ格納します。

2. 次に、元の配列全体を sort() を使って昇順に並べ替えます。計算量は O(n log n) です。

3. ソート済みの配列を先頭から順に確認しながら結果配列 res を組み立てます。値が偶数なら evenArr の位置に左から順に、奇数なら oddArr の位置に右から順に書き込みます。

この「偶数は前詰め・奇数は後ろ詰め」という配置方法により、最小の偶数から順に左側へ、最大の奇数から順に左側へと自然に配置されていき、「偶数は昇順・奇数は降順」という条件を満たす配列が完成します。

出力結果

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

[ 6, 17, 15, 12, 1, 24 ]