It is necessary to rearrange zero elements to the end, without changing the order of non-zero ones. null elements can be rearranged to the end, but the order of nonzero elements is not preserved. how to fix?

n=7 2 0 3 4 0 0 8 8 3 2 4 0 0 0 Для продолжения нажмите любую клавишу . . . 
 int a; //переменная для хранения значения перестановки for (i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (mas[j] == 0) { a = mas[j]; mas[j] = mas[i]; mas[i] = a; } } } for (i = n-1; i >=0; i--) { cout << mas[i] << " "; }

    3 answers 3

    There is a standard algorithm std::stable_partition , declared in the header file <algorithm> , which allows you to perform the task in one line.

    Below is a demonstration program.

     #include <iostream> #include <algorithm> #include <iterator> int main() { int a[] = { 2, 0, 3, 4, 0, 0, 8 }; for (int x : a) std::cout << x << ' '; std::cout << std::endl; std::stable_partition(std::begin(a), std::end(a), [](int x) { return x != 0; }); for (int x : a) std::cout << x << ' '; std::cout << std::endl; }

    Its output to the console:

     2 0 3 4 0 0 8 2 3 4 8 0 0 0

    If you need to solve a problem using cycles, then you can, for example, use such a straightforward approach, iterating over elements from the end of an array

     #include <iostream> int main() { int a[] = { 2, 0, 3, 4, 0, 0, 8 }; const size_t N = sizeof(a) / sizeof(*a); for (int x : a) std::cout << x << ' '; std::cout << std::endl; for (size_t i = N, m = N; i != 0; i--) { if (a[i] == 0) { int item = a[i - 1]; for (size_t j = i; j != m; j++) { a[j - 1] = a[j]; } a[--m] = item; } } for (int x : a) std::cout << x << ' '; std::cout << std::endl; }

    The output of this program to the console will be the same as shown above:

     2 0 3 4 0 0 8 2 3 4 8 0 0 0
    • Why are there nested loops? - Qwertiy ♦
    • @Qwertiy One cycle was superfluous. I removed it. :) - Vlad from Moscow
    • Yes not, after that cycle ; stood. And nesting is still 2. Some kind of quadratic solution instead of linear. - Qwertiy ♦
    • And in my answer to look? - Qwertiy ♦
    • @Qwertiy In general, your approach does not work. For example, when at the beginning you need to place even elements, and at the end odd elements. And I want to write a general solution, not a private one. - Vlad from Moscow

    Pretty simple linear algorithm:

    1. Pass through the array, all non-zero elements move to the beginning.
    2. The remaining tail is filled with zeros.

    http://ideone.com/KHX3Ai

     #include <iostream> using namespace std; int main() { int a[] = {2, 0, 3, 4, 0, 0, 8}; const size_t n = sizeof a / sizeof (int); size_t i; for (size_t q=i=0; q<n; ++q) if (a[q]) a[i++] = a[q]; for (; i<n; ++i) a[i] = 0; for (size_t q=0; q<n; ++q) cout << a[q] << ' '; return 0; }

      Sort :) Provided that the sort function preserves the order of equal elements. We assume that the first of the compared elements is greater than the second if the first is not zero, and the second is zero, and vice versa. If both elements are zero or not zero, they are equal.

       #include <stdio.h> #include <stdlib.h> static int cmp( const void *a, const void *b ) { int aa = *(int *)a; int bb = *(int *)b; if( !aa && bb ) return 1; if( aa && !bb ) return -1; return 0; } static void p( const char *prefix, const int *a, size_t size ) { size_t i; printf( "%-8s: ", prefix ); for( i = 0; i < size; i++ ) { printf( "%d ", a[i] ); } printf( "\n" ); } int main(void) { static int a[] = { 8, 0, 3, 4, 0, 0, 2 }; p( "before", a, sizeof(a)/sizeof(a[0]) ); qsort( a, sizeof(a)/sizeof(a[0]), sizeof(a[0]), cmp ); p( "after", a, sizeof(a)/sizeof(a[0]) ); return 0; }

      Conclusion:

       before : 8 0 3 4 0 0 2 after : 8 3 4 2 0 0 0
      • Uh ... 1. C ++. 2. There is a linear solution. - Qwertiy ♦