Given an array , write a program to move all the zero to the end of array . For example if the given array is { 1, 0, 2, 1, 0, 3, 0, 0, 5 } then it should be changed to { 1, 2, 1, 3, 5, 0, 0, 0, 0 }.
Method 1 (Modified bubble sort )
Algorithm :
1) Traverse each element of array and compare each element with the next element .
2) If current element is zero and next element is non zero then swap two element.
1) If( a[j]==0 && a[j+1]>a[j] )
swap(a[j],a[j+1])
3)Repeat the process until all the zero move to the end of array.
Implementation :
public class ZeroAtEnd {
public static void main(String args[])
{
int a[] = { 1, 0, 2, 1,
0, 3, 0, 0, 5 };
// calling the
function to move the zero at end
sortZeroAtEnd(a);
// displaying
sorted array(zero at front)
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// function to move
zero at the end
private static void sortZeroAtEnd(int[] a) {
int len = a.length;
for (int i = 0; i < len;
i++) {
for (int j = 0; j < len -
1 - i; j++) {
//if a[j] is zero
and a[j+1] is not zero then swap two element
if (a[j] == 0
&& a[j + 1] > a[j]) {
int temp = a[j + 1];
a[j
+ 1] = a[j];
a[j]
= temp;
}
}
}
}
}
Time Complexity : O(n2)
Space Complexity : O(1)
Method 2 ( Using another array )
Algorithm :
1) Traverse element of array in linear order and copy the element in temp[] array if the element is non zero.
2) Copy back all the element from the temp[] array to the front of original array [].
3) Now fill the remaining indexes with the zero at the end .
Implementation :
public class ZeroAtEnd {
public static void main(String args[])
{
int a[] = { 1, 0, 2, 1,
0, 3, 0, 0, 5 };
// calling the function to move the zero at end
sortZeroAtEnd(a);
// displaying
sorted array(zero at front)
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// function to move
zero at the end
private static void sortZeroAtEnd(int[] a) {
int len = a.length;
int temp[] = new int[len];
int j = 0;
// storing all the
non zero element in temp[] array
for (int i = 0; i < len;
i++) {
if (a[i] != 0)
temp[j++]
= a[i];
}
// shifting all the
non zero element to the front of array
for (int i = 0; i < j;
i++) {
a[i]
= temp[i];
}
// inserting zero
to the end of array
for (int i = j; i < len;
i++) {
a[i]
= 0;
}
}
}
Time Complexity : O(n)
Space Complexity : O(n)
where n is the size of input array
Method 3 ( Modifying method 2 and counting non zero elements )
Algorithm :
1) Traverse the element of input array in linear order.
2) If the encountered element a[i] is non zero then replace the element at index 'count'(a[count]) with this element.
3) Now insert 0 at the place of remaining indexes.
Implementation :
public class ZeroAtEnd {
public static void main(String args[])
{
int a[] = { 1, 0, 2, 1,
0, 3, 0, 0, 5 };
// calling the
function to sort zero at front
sortZeroAtEnd(a);
// displaying
sorted array(zero at front)
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// function to move
zero at the end
private static void sortZeroAtEnd(int[] a) {
int len = a.length;
int count = 0; // for counting non
zero element
for (int i = 0; i < len;
i++) {
// if the encountered element is non
zero then insert it at index of count
if (a[i] != 0) {
a[count]
= a[i];
count++;
}
}
// insert zero at
the remaining indexes
while (count < len) {
a[count++]
= 0;
}
}
}
Time Complexity : O(n)
Space Complexity : O(1)
Method 4 (Modified Quick Sort )
Algorithm :
Let suppose firstindex point to first element of input array and lastindex point to the last element if input array.
1) Repeat the below process until firstindex is less than lastindex.
2) Increment firstindex utlil a[firstindex]>0 and firstindex < lastindex.
3) Decrement lastindex until a[lastindex]==0 and lastindex > firstindex.
4) If firstindex is less than lastindex then swap a[firstindex] and a[lastindex].
Implementation :
public class ZeroAtEnd {
public static void main(String args[])
{
int a[] = { 1, 0, 2, 1,
0, 3, 0, 0, 5 };
// calling the function to sort zero at front
sortZeroAtEnd(a);
// displaying
sorted array(zero at front)
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// function to move
zero at the end
private static void sortZeroAtEnd(int[] a) {
int len = a.length;
len--;
int i = 0;
while (i < len) {
// increment i
until a[i]==0 and i is less than len
while (i < len
&& a[i] > 0) {
i++;
}
// decrement len
until a[j]>0 and len is greater than i
while (i < len
&& a[len] == 0) {
len--;
}
// swap the element
i and len if i is less than len
if (i < len) {
int temp = a[i];
a[i]
= a[len];
a[len]
= temp;
}
}
}
}
Time Complexity : O(n)
Space Complexity : O(1)
Please comment if you like the above post or if you find any mistake .
One traverse solution
ReplyDelete#include
int main(){
int A[]={1, 0, 2, 1, 0, 3, 0, 0, 5};
int i=0,j=8;
while(i<=j){
if(A[i]!=0){i++;
if(A[j]==0)j--;}
else {
A[i]=A[j];
A[j]=0;
i++;j--;
}
}
for(i=0;i<=8;i++){printf("%d \t",A[i]);}
return 0;}
Basic solution is to establish an inductive hypothesis that the subarray can be kept solved. Then extend the subarray by one element and maintain the hypothesis. In that case there are two branches - if next element is zero, do nothing. If next element is non-zero, swap it with the first zero in the row.
ReplyDeleteAnyway, the solution (in C# though) after this idea is optimized looks like this:
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;
}
There is a bit of thinking that leads to this solution, starting from the inductive solution which can be formally proven correct. If you're interested, the whole analysis is here: http://www.codinghelmet.com/?path=exercises/moving-zeros-to-end-of-array