C Allocating array of 500 and more longs

Question

So.. I have something like this. It is supposed to create arrays with 10, 20, 50 100 .. up to 5000 random numbers that then sorts with Insertion Sort and prints out how many comparisions and swaps were done .. However, I am getting a runtime exception when I reach 200 numbers large array .. "Access violation writing location 0x00B60000." .. Sometimes I don't even reach 200 and stop right after 10 numbers. I have literally no idea.

long *arrayIn;
int *swap_count = (int*)malloc(sizeof(int)), *compare_count = (int*)malloc(sizeof(int));
compare_count = 0;
swap_count = 0;
int i, j;
for (j = 10; j <= 1000; j*=10) {
    for (i = 1; i <= 5; i++){
        if (i == 1 || i == 2 || i == 5) {
            int n = i * j;
            arrayIn = malloc(sizeof(long)*n); 
            fill_array(&arrayIn, n);
            InsertionSort(&arrayIn, n, &swap_count, &compare_count);
            print_array(&arrayIn, n, &swap_count, &compare_count);
            compare_count = 0;
            swap_count = 0;
            free(arrayIn);
        }
    }
}

EDIT: ok with this free(arrayIn); I get this " Stack cookie instrumentation code detected a stack-based buffer overrun." and I get nowhere. However without it it's "just" "Access violation writing location 0x00780000." but i get up to 200numbers eventually

void fill_array(int *arr, int n) {
int i;
for (i = 0; i < n; i++) {
    arr[i] = (RAND_MAX + 1)*rand() + rand();
    }
}

void InsertionSort(int *arr, int n, int *swap_count, int *compare_count) {
int i, j, t;
for (j = 0; j < n; j++) {   
    (*compare_count)++;
    t = arr[j];
    i = j - 1;
    *swap_count = *swap_count + 2;
    while (i >= 0 && arr[i]>t) {    //tady chybí compare_count inkrementace
        *compare_count = *compare_count + 2;
        arr[i + 1] = arr[i];
        (*swap_count)++;
        i--;
        (*swap_count)++;
    }
    arr[i + 1] = t;
    (*swap_count)++;
    }
}

Answer 1

I am sure your compiler told you what was wrong.

You are passing a long** to a function that expects a int* at the line

fill_array(&arrayIn, n);

function prototype is

void fill_array(int *arr, int n)

Same problem with the other function. From there, anything can happen.

Always, ALWAYS heed the warnings your compiler gives you.

MAJOR EDIT

First - yes, the name of an array is already a pointer.

Second - declare a function prototype at the start of your code; then the compiler will throw you helpful messages which will help you catch these

Third - if you want to pass the address of a simple variable to a function, there is no need for a malloc; just use the address of the variable.

Fourth - the rand() function returns an integer between 0 and RAND_MAX. The code

a[i] = (RAND_MAX + 1) * rand() + rand();

is a roundabout way of getting

a[i] = rand();

since (RAND_MAX + 1) will overflow and give you zero... If you actually wanted to be able to get a "really big" random number, you would have to do the following:

1) make sure a is a long * (with the correct prototypes etc)

2) convert the numbers before adding / multiplying:

a[i] = (RAND_MAX + 1L) * rand() + rand();

might do it - or maybe you need to do some more casting to (long); I can never remember my order of precedence so I usually would do

a[i] = ((long)(RAND_MAX) + 1L) * (long)rand() + (long)rand();

to be 100% sure.

Putting these and other lessons together, here is an edited version of your code that compiles and runs (I did have to "invent" a print_array) - I have written comments where the code needed changing to work. The last point above (making long random numbers) was not taken into account in this code yet.

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

// include prototypes - it helps the compiler flag errors:
void fill_array(int *arr, int n);
void InsertionSort(int *arr, int n, int *swap_count, int *compare_count);
void print_array(int *arr, int n, int *swap_count, int *compare_count);

int main(void) {

// change data type to match function
int *arrayIn;

// instead of mallocing, use a fixed location:
int swap_count, compare_count;

// often a good idea to give your pointers a _p name:
int *swap_count_p = &swap_count;
int *compare_count_p = &compare_count;

// the pointer must not be set to zero: it's the CONTENTs that you set to zero
*compare_count_p = 0;
*swap_count_p = 0;

int i, j;
for (j = 10; j <= 1000; j*=10) {
    for (i = 1; i <= 5; i++){
        if (i == 1 || i == 2 || i == 5) {
            int n = i * j;
            arrayIn = malloc(sizeof(long)*n); 
            fill_array(arrayIn, n);
            InsertionSort(arrayIn, n, swap_count_p, compare_count_p);
            print_array(arrayIn, n, swap_count_p, compare_count_p);
            swap_count = 0;
            compare_count = 0;
            free(arrayIn);
        }
    }
}
return 0;
}

void fill_array(int *arr, int n) {
int i;
for (i = 0; i < n; i++) {
    // arr[i] = (RAND_MAX + 1)*rand() + rand(); // causes integer overflow
    arr[i] = rand();
    }
}

void InsertionSort(int *arr, int n, int *swap_count, int *compare_count) {
int i, j, t;
for (j = 0; j < n; j++) {   
    (*compare_count)++;
    t = arr[j];
    i = j - 1;
    *swap_count = *swap_count + 2;
    while (i >= 0 && arr[i]>t) {    //tady chybí compare_count inkrementace
        *compare_count = *compare_count + 2;
        arr[i + 1] = arr[i];
        (*swap_count)++;
        i--;
        (*swap_count)++;
    }
    arr[i + 1] = t;
    (*swap_count)++;
    }
}

void print_array(int *a, int n, int* sw, int *cc) {
  int ii;
  for(ii = 0; ii < n; ii++) {
    if(ii%20 == 0) printf("\n");
    printf("%d ", a[ii]);
  }
  printf("\n\nThis took %d swaps and %d comparisons\n\n", *sw, *cc);
}

Answer 2

You are assigning the literal value 0 to some pointers. You are also mixing "pointers" with "address-of-pointers"; &swap_count gives the address of the pointer, not the address of its value.

First off, no need to malloc here:

int *swap_count = (int*)malloc(sizeof(int)) ..

Just make an integer:

int swap_coint;

Then you don't need to do

swap_coint = 0;

to this pointer (which causes your errors). Doing so on a regular int variable is, of course, just fine.

(With the above fixed, &swap_count ought to work, so don't change that as well.)

Answer 3

As I told in the comments, you are passing the addresses of pointers, which point to an actual value.

With the ampersand prefix (&) you are passing the address of something. You only use this when you pass a primitive type.

E.g. filling the array by passing an int. But you are passing pointers, so no need to use ampersand.

What's actually happening is that you are looking in the address space of the pointer, not the actual value the pointer points to in the end. This causes various memory conflicts.

Remove all & where you are inputting pointers these lines:

fill_array(&arrayIn, n);
InsertionSort(&arrayIn, n, &swap_count, &compare_count);
print_array(&arrayIn, n, &swap_count, &compare_count);

So it becomes:

fill_array(arrayIn, n);
InsertionSort(arrayIn, n, swap_count, compare_count);
print_array(arrayIn, n, swap_count, compare_count);

I also note that you alloc memory for primitive types, which could be done way simpler:

int compare_count = 0;
int swap_count = 0;

But if you choose to use the last block of code, DO use &swap_count and &compare_count since you are passing primitive types, not pointers!