C: Array not allocating more memory correctly

Question

I'm fairly new to C and I'm working on a project. Given an integer array, I want to move all the zeros in it to the left of the array with the rest of the elements in any order to the right of all the zeros. The basic idea of my algorithm is to count the number of zeros in the array, create a new array with the number of zeros in it from the old array, and then "append" the rest of the non-zero integers onto this array. And then of course I print finished product.

int main(int argc, const char * argv[]) {
    int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
    int n = 10, count = 0;

    // counts the number of 0's in the original array
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == 0)
        {
            ++count;
        }
    }

    // creates a new array and makes each element 0
    int *array = NULL;
    for (int j = 0; j < count; ++j)
    {
        array = realloc(array, (j + 1) * sizeof(int));
        array[j] = 0;
    }

    // adds the nonzero elements of the array to the new array
    for (int l = count; l < n; ++l)
    {
        array = realloc(array, l * sizeof(int)); // getting an error here
        if (a[l] != 0)
        {
            array[l+count] = a[l];
        }
    }

    // prints the array out in a nice format
    printf("%s", "{");
    for (int k = 0; k < n-1; ++k)
    {
        printf("%d%s", array[k], ",");
    }

    printf("%d", array[n-1]);
    printf("%s", "}\n");


    free(array);
    return 0;
}

I'm getting a "Thread 1: EXC_BAD_ACCESS (code=1, address=0x40)" error when I run this code. I think it's got to do something with invalid pointers to the new array, but I'm not sure how to fix it.

Answer 1

Before you start to hack away, take your time to consider the actual problem, which you have described as:

count the number of zeros in the array, create a new array with the number of zeros in it from the old array, and then "append" the rest of the non-zero integers onto this array.

Your comments say what the code should do, yet the code does something entirely different. Your algorithm to solve the problem is wrong - this, and nothing else, is the cause of the bugs.

To begin with, if the new array should contain all zeroes of the old array plus all non-zeroes, then common sense says that the new array will always have the same size as the old array. You don't even need to use dynamic memory allocation.

The code you have creates a new array and discards the old one, in the same memory location, over and over. This doesn't make any sense. On top of that, it is very ineffective to call realloc repeatedly in a loop.

You should do something like this instead:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int main(int argc, const char * argv[]) {
    int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
    const int n = 10; 

    // counts the number of 0's in the original array
    int zeroes = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == 0)
        {
            ++zeroes;
        }
    }

    // creates a new array and makes each element 0
    // there's actually no need to allocate this dynamically at all...
    int *array = calloc(1, sizeof(int[n]) ); 
    assert(array != NULL);

    // skip zeroes, ie "move the zeroes from the original array"
    int* not_zeroes = array + zeroes; // point at first item to contain "not zeroes"

    // adds the non-zero elements of the original array to the new array
    for (int i = 0; i < n; ++i)
    {
      if(a[i] != 0)
      {
        *not_zeroes = a[i]; 
        not_zeroes++;
      }
    }

    // prints the array out in a nice format
    printf("%s", "{");
    for (int i = 0; i < n; ++i)
    {
        printf("%d,", array[i]);
    }
    printf("}\n");


    free(array);
    return 0;
}

Answer 2

Other answers address your immediate issue, that

            array[l+count] = a[l];

attempts to access outside the bounds of the allocated space to which array points. I'll focus instead on your approach to the problem, which is flawed.

Dynamic memory allocation is comparatively expensive. You do not want to do any more than necessary, and it is particularly poor form to reallocate many times to increase by small increments each time, as you do.

Since you know at compile time how many elements you will need, dynamic allocation is altogether unnecessary here. You could instead do this:

int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
int array[10] = { 0 };

(Note also here that when an array initializer is provided, any array elements it does not explicitly initialize are initialized to 0.)

Even if you did not know at compile time how many elements you would need, it would be far better to perform the whole allocation in one chunk. Moreover, if you did that via calloc() then you would get automatic initialization of the allocated space to all-zeroes.

Answer 3

The problem is with array[l+count] = a[l]; right when you are done allocating your 'zero-array' it's size is 3 and then you try to access (l + count)'th position which is 6.

And even if you have fixed those issues with memory it still wouldn't work because a[l] and further may still be zeros. (Your initial array is doesn't have zeroes in the beggining, remember?)

And there is a couple of suggestions: use calloc() to build your initial array of zeros because as man states:

The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to zero

First allocate then set because operations with memory are quite taxing for performance. It would be better for you to first allocate some memory and work with it instead of reallocating it each step. It would be much easier to keep track of as well.

Answer 4

About your algorithm:

I think u don't need to create a new array, just use a int tmp as swap area, and a int foundZeroCount as index, u swap 2 numbers at a time.

About memory allocation:

If u want to allocate memory for a fixed size array, just use malloc() to allocate array once, later when u need to extend the array, just call realloc() once.

About memory reset:

Just use memset(), and don't need a loop.

Suggestion - about c programming

Try improve your c basic, especially about array / pointer / memory, and try to know more functions from glibc.

Books like <The c programming language 2nd>, GNU c library document, and <The linux programming interface> would be useful, I guess.

Answer 5

array[l+count] = a[l];

This accesses the memory block that array points at beyond its allocated size. You have to do it differently, using a second index:

// adds the nonzero elements of the array to the new array
int l = count;

for (int j=0; j < n; ++j)
{
    if (a[j] != 0)
    {
        array = realloc(array, (l+1) * sizeof(int));
        array[l] = a[j];
        ++l;
    }
}

Answer 6

The count is known before defining the array. You can allocate memory using malloc as shown below.

array = malloc( count * sizeof(int)).

The error indicates you are trying to access address 0x40. This indicates one of the pointer has become NULL and you are trying to dereference ptr+0x40.