JavaScriptで配列内の0をすべて末尾に移動するインプレースアルゴリズムの実装方法

問題概要

整数の配列 arr が与えられたとします。求められているのは、元の配列を直接書き換える（インプレース）形ですべての 0 を配列の末尾へ移動させる関数を実装することです。

その際、0 以外の要素どうしの相対的な順序は崩してはいけません。

例として、入力配列が次のような場合を考えてみましょう。

const arr = [0, 11, 0, 22, 67];

この配列は、以下のように変換される必要があります。

const output = [11, 22, 67, 0, 0];

アルゴリズムのアプローチ

この問題は二ポインタ（Two Pointers）のテクニックを使うことで効率的に解けます。考え方は次のとおりです。

• 「次に非ゼロ要素を置くべき位置」を示すインデックス j を用意する（初期値は 0）。
• 配列を先頭から順に走査し、arr[i] が 0 以外なら i と j の要素を入れ替えて j を進める。
• 走査終了後、j 以降の残りの位置にはすべて 0 を代入する。

この方法なら時間計算量は O(n)、空間計算量は O(1) となり、追加の配列も不要です。さらに、非ゼロ要素の出現順序も自然に保たれます。

コード例

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

const arr = [0, 11, 0, 22, 67];
const moveZeroToEnd = (arr = []) => {
    const swap = (array, ind1, ind2) => {
       const temp = array[ind1];
       array[ind1] = array[ind2];
       array[ind2] = temp;
    };
    let j = 0;
    for (let i = 0; i < arr.length; ++ i) {
       if (arr[i] !== 0) {
          swap(arr, i, j++);
       }
    }
    while (j < arr.length) {
       arr[j++] = 0;
    };
};
moveZeroToEnd(arr);
console.log(arr);

コードの解説

• swap関数：指定された2つのインデックスの要素を、一時変数 temp を介して入れ替えます。
• メインのforループ：i は走査用、j は「非ゼロ要素を配置する位置」を担当します。0 以外の値が見つかるたびに、それを先頭側へ詰めていくイメージです。
• 最後のwhileループ：非ゼロ要素をすべて前に寄せ終えた後、残りの位置を 0 で埋めます。

別のシンプルな書き方（非インプレース）

厳密なインプレース処理が不要な場合は、filter と concat を組み合わせるとより簡潔に記述できます。

const moveZeroToEndSimple = (arr = []) =>
  [...arr.filter(x => x !== 0), ...arr.filter(x => x === 0)];

ただしこの方法は新しい配列を生成するため、メモリ効率の面ではインプレース版に劣ります。大規模なデータやパフォーマンスが重視される場面では、冒頭で紹介したスワップ方式が適しています。

出力結果

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

[11, 22, 67, 0, 0]