JavaScriptで配列の奇数と偶数を分けて並べ替える方法

はじめに

本記事では、整数の配列を受け取り、すべての奇数を先頭に、偶数をその後に配置するように並べ替えるJavaScript関数の実装方法を解説します。

要件の整理

関数に求められる条件は以下のとおりです。

• 入力として整数の配列を受け取る
• すべての奇数を偶数より前に配置する
• 奇数同士・偶数同士の相対的な順序は問わない

入力例と出力例

たとえば、次の配列が入力されたとします。

const arr = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1];

この場合、正しい出力のひとつは次のようになります（奇数がすべて偶数より前に来ていればよく、正解は複数存在します）。

const output = [
1, 3, 5, 7, 9,
1, 0, 2, 4, 6,
8, 0
];

実装コード

以下は、挿入ソートの考え方を応用した実装例です。隣り合う要素を比較し、「偶数の直後に奇数」が続く場合は交換することで、奇数を前へ移動させていきます。

const arr = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1];
const sortOddEven = (arr = []) => {
    let i = 0, j, temp;
    while (i < arr.length - 1) {
        j = i;
        while (!(arr[j] % 2) && arr[j + 1] % 2) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            if (!j) {
                break;
            };
            j--;
        };
        i++;
    };
};
sortOddEven(arr);
console.log(arr);

コードの解説

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

• 外側のwhileループで配列を先頭から順に走査します。
• 内側のwhileループでは、arr[j]が偶数（arr[j] % 2が0）で、かつarr[j + 1]が奇数の場合に隣接要素を交換し、奇数を1つずつ前に移動させます。
• jが0になったらそれ以上左へ移動できないため、ループを抜けます。

なお、JavaScriptの%演算子は負の数に対して負の値を返す点に注意が必要です。たとえば-3 % 2は-1となるため、負の数が含まれる可能性がある場合はn % 2 !== 0で判定するのが安全です。

実行結果

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

[
    1, 3, 5, 7, 9,
    1, 0, 2, 4, 6,
    8, 0
]

別のシンプルな実装

より簡潔に書きたい場合は、filter()を組み合わせる方法も有効です。

const sortOddEven = (arr = []) => [
    ...arr.filter(n => n % 2 !== 0),
    ...arr.filter(n => n % 2 === 0)
];

この方法では元の配列は変更されず、新しい配列が返されます。計算量はO(n)で、隣接交換方式（最悪O(n²)）よりも効率的に処理できます。

まとめ

奇数を先頭に偶数を後ろへ並べ替える処理は、隣接要素の交換を繰り返す方法でも、filter()で振り分ける方法でも実現できます。元の配列をその場で変更したいか、新しい配列を作りたいか、パフォーマンス要件などを考慮して使い分けるとよいでしょう。