Move Zero Eelements in an Array to the End

From Software Engineers Wiki
Jump to: navigation, search

Move elements with value zero to the end of the array

Answer 1: Unstable

Following is quick approach which shakes up the order of the elements (unstable). Basic idea is scan from the end, and replace zero element with non-zero element. This moves only zero element.

void move_zero_to_end_unstable(int *data, int size)
{
        int *p_nonzero;
        int *p_cur;

        /* find first non-zero element from the end */
        for (p_nonzero = data + size - 1; p_nonzero > data; --p_nonzero)
                if (*p_nonzero)
                        break;
        if (p_nonzero == data)
                return;

        /* move zero to the end */
        for (p_cur = p_nonzero - 1; p_cur >= data; --p_cur) {
                if (*p_cur == 0) {
                        *p_cur = *p_nonzero;
                        *p_nonzero-- = 0;
                }
        }
}

Answer 2: Stable

If the require is to keep the order of the element, above approach does not work. This may requires more moves compared to above solution because it needs to move every elements after first zero element.

void move_zero_to_end_stable(int *data, int size)
{
        int *p_end = data + size;
        int *p_zero;
        int *p_cur;

        /* find first non-zero element from the end */
        for (p_zero = data; p_zero < p_end; ++p_zero)
                if (*p_zero == 0)
                        break;
        if (p_zero == p_end)
                return;

        /* move non-zero element */
        for (p_cur = p_zero + 1; p_cur < p_end; ++p_cur)
                if (*p_cur != 0)
                        *p_zero++ = *p_cur;

        /* fill the trailing zeros */
        while (p_zero < p_end)
                *p_zero++ = 0;
}
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox