Move zeroes

Push every zero to the end in place, in one pass, without disturbing the order of the other values.

The idea

write marks the end of the non-zero region built so far. Scan with read: whenever a non-zero value turns up, swap it down into the write slot and advance write. The zeros left behind by the swaps end up pushed to the back automatically.

Code

public static void MoveZeroes(int[] a) {
    int write = 0;
    for (int read = 0; read < a.Length; read++) {
        if (a[read] != 0) {
            (a[write], a[read]) = (a[read], a[write]);
            write++;
        }
    }
}

Tips

• When read and write are the same index the swap does nothing, which is harmless.
• This write-pointer pattern is the same one used to remove duplicates, or a given value, from an array in place.

In the .NET library

A version that overwrites instead of swapping (copy a[read] to a[write], then zero-fill the tail) does one fewer comparison per step but needs a second pass to fill the zeros.