JavaScriptで配列内のすべての0（ゼロ）を末尾へ移動するアルゴリズムの実装方法

はじめに

本記事では、配列を受け取り、その中に存在するすべての0（ゼロ）を余分なメモリ領域を使用せずに配列の末尾へ移動させる関数の実装方法を解説します。この問題は、フロントエンドエンジニアの採用面接などでもよく出題される定番のアルゴリズム課題の一つです。

ここでは、Array.prototype.splice()とArray.prototype.push()を組み合わせたシンプルなアプローチを紹介します。

実装コード

const arr = [34, 6, 76, 0, 0, 343, 90, 0, 32, 0, 34, 21, 54];

const moveZero = (arr) => {
  for (let ind = 0; ind < arr.length; ind++) {
    const el = arr[ind];
    if (el === 0) {
      // 0を見つけたら配列から削除し、末尾に追加
      arr.push(arr.splice(ind, 1)[0]);
      // 要素が1つ減ったため、インデックスを戻す
      ind--;
    }
  }
};

moveZero(arr);
console.log(arr);

処理の流れ

この関数は、以下の手順で動作します。

1. 配列を先頭から走査する：forループを使って、配列の各要素を先頭から順番にチェックしていきます。

2. 0を検出したら末尾へ移動：要素が0だった場合、splice(ind, 1)でその要素を配列から取り除き、同時にpush()で配列の末尾へ追加します。新しい配列を作成しないため、メモリを節約できる「in-place（その場での処理）」な操作となっています。

3. インデックスを調整する：splice()によって要素が1つ削除されると、後続の要素が前に詰められます。そこでind--とすることでインデックスを1つ戻し、削除後に同じ位置へ移動してきた要素のチェック漏れを防いでいます。

実行結果

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

[34, 6, 76, 343, 90, 32, 34, 21, 54, 0, 0, 0, 0]

すべての0が配列の末尾に集められ、それ以外の要素は元の順序を保ったまま並んでいることが確認できます。

注意点：計算量について

このアプローチでは、0が見つかるたびにsplice()が実行されます。splice()は配列内の要素を詰め直す必要があるためO(n)の計算量を持ち、最悪ケース（配列がほぼすべて0の場合）では全体の時間計算量がO(n²)になります。

パフォーマンスを重視する場合は、双方向ポインタ（Two Pointers）を活用する手法がおすすめです。非ゼロ要素を配列の前方へ順に詰めていき、最後に残りの位置を0で埋めることで、O(n)の時間計算量・O(1)の空間計算量で処理できます。大規模なデータを扱う際には、ぜひこちらの手法も検討してみてください。