7
\$\begingroup\$

I would like to write a function in C that turns all negative values into zeros then shifts the positive numbers to the beginning of the array, maintaining the order of the positive integers in the array.

void shift_positives(int values[], int num_values) {
    int i;
    int last_zero = 0;
    int j;
    for (j = 0; j < num_values; j++) {
        if (values[i] < 0) values[i] = 0;

        if (values[j] > 0) {
            for (i = last_zero; i < j; i++) {
                if (values[i] == 0) {
                    last_zero = i;
                    break;
                }
            }
            if (last_zero < j) {
                values[last_zero] = values[j];
                values[j] = 0;
            }
        }   
    }
}

My issue with this is that it runs at \$O(N^2)\$ because of the inner for loop. Is there a more efficient way to do this?

\$\endgroup\$
1
  • \$\begingroup\$ So much easier with C++: std::fill(std::remove_if(first, last, [](int v) { return v < 0; }), last, 0); \$\endgroup\$
    – Joe
    Sep 8, 2015 at 9:14

4 Answers 4

16
\$\begingroup\$

There is a much more efficient way to do this, involving two pointers, a 'right', and a 'left' pointer. They both start at 0.

The trick is to inspect the value at the right pointer. If it is negative, increment the right pointer. If it is positive, move it to the left pointer, and increment both pointers.

This allows you to move all the positive values to the beginning of the array, in the order they were found. All you need to do then, is to zero out all the values from the left pointer to the right....

I assume that 0 is considered to be 'not positive'....

void shift_positives(int values[], int num_values) {
    int left = 0;
    for (int right = 0; right < num_values; right++) {
        if (values[right] > 0) {
            values[left++] = values[right];
        }
    }
    while (left < num_values) {
        values[left++] = 0;
    }
}

This performs the operation in \$O(n)\$ time. See it running on ideone

\$\endgroup\$
7
\$\begingroup\$

Your function has undefined behaviour. You can see this clearly if you just examine the variable i.

int i;
…
for (…) {
    if (values[i] < 0) …
    …
}

You're using i before it has been initialized. If your function doesn't crash, consider yourself lucky, and if it actually produces the intended result, consider yourself doubly lucky.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ s/lucky/unlucky. It would probably stop working at the worst moment. \$\endgroup\$ Sep 8, 2015 at 10:29
2
\$\begingroup\$

The algorithm I would use would be one that shifts the positives to the beginning of the array, then changing all the other elements to be 0 (because they are non-positive). It keeps track of which elements are positive by looping to find the positives! and keeping track of how many via the variable pos. then it loops from pos to num_values to make all the other discarded values zero.

This algorithm accomplishes the task in one pass: j counts up from 0 to num_values.

void shift_positives(int values[], int num_values) {
    int pos = 0;
    int j;
    for (j = 0; j < num_values; j++) {
        if (values[j] > 0) {
            values[pos]=values[j];
            pos++;
        }  
    }
    for(j=pos;j<num_values;j++)
        values[j]=0;
}
\$\endgroup\$
0
1
\$\begingroup\$

I think @rofl hit the nail right on the head, except that this piece of reviewing code is aiming a little change on an unneeded loop.

  1. Instead of:

    for (int right = 0; right < num_values; right++) {
        if (values[right] > 0) {
            values[left++] = values[right];
        }
    }
    

    use:

     int temppoint=-1;
     for (int right = 0; right < num_values; right++)
         if (values[right] > 0)
             temppoint=(temppoint==-1)?right:temppoint;
         else if(temppoint!=-1)
         {
             memcpy(values+left,values+temppoint,sizeof(int)*(right-temppoint));
             left+=right-temppoint;
             temppoint=-1;
         }
    
  2. Instead of:

    while (left < num_values) {    
        values[left++] = 0;
    }
    

    use:

    memset(values+left,0,sizeof(int)*(num_values-left+1));
    

  • Code must be headed by <string.h>. That might reduce the pain of mutating values one after another, and transforming data rather as a whole. Theoretically the complexity is barely optimised, and practically it narrows low-level execution cycles.

    And that is concerning the main code as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.