【JavaScript】偶数と奇数をそれぞれ偶数番目・奇数番目のインデックスに並べ替える方法

問題の概要

数値の配列を受け取り、その要素を並べ替えるJavaScript関数を作成する必要があります。関数に入力される配列には、次の2つの特別な性質があります。

• 配列の長さは必ず偶数である。
• 配列内の偶数の個数と奇数の個数は常に等しい(つまり、どちらも配列の長さの半分と一致する)。

この関数は、配列の要素をシャッフルし、すべての偶数が偶数番目のインデックス(0, 2, 4…)に、すべての奇数が奇数番目のインデックス(1, 3, 5…)に配置されるようにしなければなりません。

なお、この問題には正解が複数存在する場合があります。そのため、正しい答えのどれか1つを見つけられれば十分です。

解法のアプローチ

この問題は、2つのポインタ(インデックス)を利用したシンプルなアルゴリズムで効率的に解くことができます。手順は以下のとおりです。

• 偶数用のポインタ even を 0(先頭の偶数インデックス)、奇数用のポインタ odd を 1(先頭の奇数インデックス)で初期化します。
• even の位置にある値が奇数で、かつ odd の位置にある値が偶数である場合、両者を交換し、両方のポインタを2つずつ進めます。
• それ以外の場合は、すでに条件を満たしている側のポインタだけを2つずつ進めて、次の候補位置へ移動します。

この方法では各要素が高々1回ずつ処理されるため、時間計算量は O(n)、追加のメモリ使用量は O(1) という非常に効率的な実装になります。

コード例

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

const arr = [1, 2, 3, 4, 5, 6];
const arrangeToIndices = (arr = []) => {
    let [even, odd] = [0, 1];
    while (even < arr.length && odd < arr.length) {
        if (arr[even] % 2 === 1 && arr[odd] % 2 === 0) {
            [arr[even], arr[odd]] = [arr[odd], arr[even]];
            [even, odd] = [even + 2, odd + 2];
        } else {
            if (0 === arr[even] % 2){
                even += 2;
            };
            if (1 === arr[odd] % 2){
                odd += 2;
            };
        };
    };
    return arr;
};
console.log(arrangeToIndices(arr));

出力結果

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

[ 2, 1, 4, 3, 6, 5 ]

コードのポイント解説

• 分割代入による初期化: let [even, odd] = [0, 1]; のように書くことで、2つのポインタを簡潔に初期化できます。
• 交換処理: 分割代入 [arr[even], arr[odd]] = [arr[odd], arr[even]]; を使うことで、一時変数なしでスワップを実現しています。
• 2ずつの移動: 偶数インデックス同士・奇数インデックス同士だけを比較対象とするため、ポインタは常に2ずつ進みます。
• 終了条件: どちらかのポインタが配列の範囲外に出た時点で、すべての位置が正しく整列されたことになります。

このアルゴリズムを使えば、入力配列をその場(in-place)で並べ替えられるため、大きな配列に対しても高いパフォーマンスを発揮します。