Here the question is to put all the zeroes to the end of the array. I've written the code below, but after passing (arr, n) to the pushzero() function, when I try to print the array, it does nothing, and the value of n changes to zero after calling the pushzero() function.

#include <bits/stdc  .h>

using namespace std;

void pushzero(int arr[], int n) {   
    for (int i = 0; i < n; i  ) {   
        for (int j = 0; j < i   1; j  ) {
            if (arr[j] == 0) {
                swap(arr[j 1], arr[j]);
            }
        }
    }
}

int main() {
    int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    for (int i = 0; i < n; i  ) {
        cout << arr[i] << " " << "\n";
    }
    pushzero(arr, n);
    
    for (int j = 0; j < n; j  ) { // n is 0 here
        cout << arr[j] << " ";
    }
    return 0;
}

CodePudding user response：

The code has undefined behavior because the inner loop in pushzero iterates too far:

• in the last iteration of the outer loop of pushzero, i has the value n - 1
• the last iteration of the inner loop, j has the value i, hence n - 1,
• if the test arr[j] == 0 is true, which will happen since there are multiple zeroes in the array, swap will be called to exchange the values of arr[j] and arr[j 1], hence reading and modifying arr[n] which is beyond the end of the array.

This undefined behavior may have surprising consequences, such as the behavior you observe, possibly because n is stored in stack memory just after the array arr, an indication that you disabled optimisations.

Changing the loop test to j < i fixes the out of bounds access but does not achieve your goal. You should write j < n - i - 1 for proper operation.

Here is a modified version:

#include <bits/stdc  .h>

using namespace std;

void pushzero(int arr[], int n) {   
    for (int i = 0; i < n; i  ) {   
        for (int j = 0; j < n - i - 1; j  ) {
            if (arr[j] == 0) {
                swap(arr[j 1], arr[j]);
            }
        }
    }
}

int main() {
    int arr[] = { 2, 6, 0, 0, 1, 9, 0, 8, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    for (int i = 0; i < n; i  ) {
        cout << arr[i] << " ";
    }
    cout << "\n";

    pushzero(arr, n);
    
    for (int i = 0; i < n; i  ) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

The above implementation is suboptimal as it has O(N²) complexity. Below is a simpler one with linear execution time:

void pushzero(int arr[], int n) {   
    int i, j;
    for (i = j = 0; i < n; i  ) {   
        if (arr[i] != 0) {
            arr[j  ] = arr[i];
        }
    }
    while (j < n) {   
        arr[j  ] = 0;
    }
}

Or using the swap() function with slightly more work:

void pushzero(int arr[], int n) {  
    for (int i = 0, j = 0; i < n; i  ) {   
        if (arr[i] != 0) {
            swap(arr[i], arr[j  ]);
        }
    }
}

You can also use a more idiomatic C solution, as suggested by @PaulMcKenzie:

#include <algorithm>

void pushzero(int arr[], int len) {   
    std::stable_partition(arr, arr   len, [](int n) { return n != 0; });
}

CodePudding user response：

You could do it by using 0 as a pivot element and whenever you see a non zero element you will swap it with the pivot element. So all the non zero element will come at the beginning.

void pushzero(int arr[], int n) {  
    int j =0; 
    for (int i = 0; i < n; i  ) {   
        if(arr[i] != 0) {
            swap(arr[i], arr[j]);
            j  ;
        }
    }
}

Demo: https://godbolt.org/z/oMdxfdWjG