by Zoran Horvat

Jun 11, 2015

Given an unsorted array of integer numbers, write a function which transforms the array so that all numbers that are equal to zero are moved towards the end of the array. Non-zero elements should be moved to the beginning of the array, while still preserving their relative order.

Example: Suppose that array [4, 1, 0, 2, 0, 0, 5, 3] is passed to the function. After the function executes, the array should contain values [4, 1, 2, 5, 3, 0, 0, 0].

We could approach this problem from the mathematical induction point of view. The goal of the exercise is to produce an array which has the quality of having its zeros pushed towards its end. The mathematical induction now comes to the picture. If we could start with an initial array which possesses the quality we want, and if we could add one element at the time to the array, while in each step preserving the quality, then we could gradually build the final, complete array which also possesses the same quality.

This idea sounds very simple and it is also simple to prove that it will work correctly. In mathematical induction we normally start with the initial state. In this example, we can say that an empty subarray satisfies the constraint from the problem statement. It contains no elements, so there is no element to violate the constraint.

Similarly, a subarray with only one element also possesses the desired quality. Being zero or non-zero, this single element cannot break the constraint.

So the problem boils down to solving the case with multiple elements in the subarray. We can set the inductive hypothesis that the subarray with k (k > 0) elements satisfies the constraint. Our goal is to extend the subarray with the element at position k+1 in such way that the quality is preserved.

This operation will then depend on the value of the element at position k+1. If that element is zero, then it will not violate the constraint and the k+1 subarray will still possess the required quality. Picture below shows this case.

If the element at position k+1 is non-zero, then it will violate the constraint and cause the k+1 subarray to lose the quality of having all zeros near the end of the array. Our task is then to restore that quality. We can easily do that by swapping the non-zero element with the first zero element in the sequence of zeros, as shown in the picture below. In that way, the sequence of zeros will occupy the end of the array and the requested quality will be restored again.

This operation has one special case. It could happen that we encounter a non-zero element without visiting any zero element before it. In that case, the non-zero element is not violating the array quality and there is nothing to do with it. This case is shown in the following picture.

When all the elements of the array are exhausted, the complete array will be brought into state with all zero elements moved to its end. This completes the inductive proof of correctness of this algorithm.

Below is the pseudocode of the function which moves zeros to the end of the array.

```
function MoveZeros(a in/out, n)
-- a – array of integers
-- n – length of the array
Begin
i = 0 -- index of the first zero
while i < n and a[i] <> 0
i = i + 1
j = i -- index of next number to process
while j < n
begin
if a[j] <> 0 then
begin
a[i] = a[j]
a[j] = 0
i = i + 1
end
j = j + 1
end
end
```

This function will work properly on any array, and that is what we have proved using mathematical induction. But the problem with this function that it is a bit complicated. We can make it shorter by noticing that the first loop, which looks for the first occurrence of zero in the array, is not required. Without that loop, the non-zero element will just be swapped with itself, which is a null operation and has no effect. This case is presented in the figure below.

Bottom line is that we can eliminate the first loop entirely:

```
function MoveZeros(a in/out, n)
-- a – array of integers
-- n – number of elements
begin
i = 1 -- next place to put non-zero element
for j = 1 to n
begin
if a[j] <> 0 then
begin
swap(a[i], a[j])
i = i + 1
end
end
end
function swap(x in/out, y in/out)
begin
temp = x
x = y
y = temp
end
```

This implementation relies on a single loop in the function, but this time it must implement the proper swap function. Previous solution didn’t have to perform full swap of values because we knew that one of the values is zero.

Anyway, this implementation leads us to even better simplification. The whole process until this moment was driven by an inductive hypothesis that subarray up to the current position is solved. This means that all zeros that existed in that subarray are properly moved to its end. At this point, we are ready to relax the constraints.

Let’s say that we only want the final array to have this quality of having its zeros moved to the end. That is precisely what the problem statement says.

So, what can we do with the previous solution to make it simpler? The answer is that we don’t have to move zeros immediately. We can leave that step for the end, simply because we know that all values to move are equal to zero. Here is the solution:

```
function MoveZeros(a in/out, n)
-- a – array of integers
-- n – number of elements
begin
i = 1 – index where to put next non-zero
for j = 1 to n
if a[j] <> 0 then
begin
a[i] = a[j]
i = i + 1
end
while i <= n
a[i] = 0
end
```

This solution is both simple and efficient. Every element of the array is copied at most once. It is based on the idea that inductive hypothesis can be relaxed, provided that it is re-established again before completing the operation.

Below is the C# Console application with all three distinct implementations of the function that were discussed in this exercise.

```
using System;
namespace MoveZeros
{
class Program
{
private static Random random = new Random();
static int[] CreateArray(int n)
{
int[] array = new int[n];
for (int i = 0; i < n; i++)
array[i] = random.Next(6);
return array;
}
static void Print(int[] a)
{
foreach (int value in a)
Console.Write("{0,2}", value);
Console.WriteLine();
}
static void MoveZerosFull(int[] a)
{
int i = 0;
while (i < a.Length && a[i] != 0)
i++;
for (int j = i; j < a.Length; j++)
{
if (a[j] != 0)
{
a[i++] = a[j];
a[j] = 0;
}
}
}
static void MoveZerosOneLoop(int[] a)
{
int i = 0;
for (int j = 0; j < a.Length; j++)
if (a[j] != 0)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
}
}
static void MoveZeros(int[] a)
{
int i = 0;
for (int j = 0; j < a.Length; j++)
if (a[j] != 0)
a[i++] = a[j];
while (i < a.Length)
a[i++] = 0;
}
static void Main(string[] args)
{
while (true)
{
Console.Write("Enter number of elements (0 to exit): ");
int n = int.Parse(Console.ReadLine());
if (n == 0)
break;
int[] a = CreateArray(n);
Print(a);
MoveZeros(a);
Print(a);
Console.WriteLine();
}
}
}
}
```

When the application is run, it produces output like this:

```
Enter number of elements (0 to exit): 1
0
0
Enter number of elements (0 to exit): 1
2
2
Enter number of elements (0 to exit): 2
0 1
1 0
Enter number of elements (0 to exit): 5
0 2 3 0 5
2 3 5 0 0
Enter number of elements (0 to exit): 10
0 0 2 2 4 0 5 1 5 0
2 2 4 5 1 5 0 0 0 0
Enter number of elements (0 to exit): 20
2 4 0 1 5 0 3 4 4 5 3 1 5 0 0 4 5 3 5 4
2 4 1 5 3 4 4 5 3 1 5 4 5 3 5 4 0 0 0 0
Enter number of elements (0 to exit): 0
```

In this exercise we have seen one seemingly abstract problem. But that doesn't have to be that way. Imagine a messaging system in which a number of messages arrive for processing. The task could be to move all messages with empty payload to the end of the queue, so that messages carrying actual payload have precedence. Such request would then be almost identical to this exercise.

While solving theoretical problems, it is very important to keep the practical perspective. Virtually every theoretical problem can appear in practice, often obscured by the boring implementation details of the system at hand. Our ability to separate the core problem from implementation details may then be of great importance when searching for the efficient solution.

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- Substituting the Builder with the Sequence of Factory Methods
- Custom Implementation of the Option/Maybe Type in C#
- Pros and Cons of Multiple Constructors
- Defensive Design: An Experiment
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design