# Thread: Help - error sorting dynamically allocated 2D integer array

1. ## Help - error sorting dynamically allocated 2D integer array

Hi,
First time posting on this forum and I have an embarrassingly newbie question about using qsort with dynamically allocated 2D arrays.

I need to sort a large dynamically allocated 2D integer array where the number of rows is determined at run time and the number of columns is fixed at 4. I want to sort the array based on the values in the last two columns. After reading several discussion threads on dereferencing pointers, I tried writing a simple program to test my compare function with a 10 x 4 array. It keeps crashing at run time and as a biologist who probably shouldn't be messing with programming, I can't for the life of me figure out why.

I have pasted the code below and would greatly appreciate your time and wisdom in figuring out the bug. Many thanks in advance!

Code:
```#include <stdio.h>
#include <stdlib.h>

static int comp(const void *a, const void *b) {
int **p1 = (int**)a;
int **p2 = (int**)b;
int *arr1 = *p1;
int *arr2 = *p2;

int diff1 = arr1[3] - arr2[3];
if (diff1) return diff1;
return arr2[2] - arr1[2];
}

int main(void)
{

int i;

int **array = (int**)malloc(sizeof(int *) * 10);
for(i = 0; i <  10; i++){
array[i] = (int*)malloc(sizeof(int) * 4);
}

for(i = 0; i < 10; i++)
{
array[i][0] = i ;
array[i][1] = i * 2;
array[i][2] = rand() % 2;
array[i][3] = rand() % 10;
}

qsort(array, 10, sizeof(int) * 4, comp);

for(i = 0; i < 10; i++)
{
free(array[i]);
}
free(array);

return 0;
}```

2. Biologist? Very interesting field. Taking a herpetology course at Elon University as part of a college access program made me change my major to something more environment-related so I respect that. You should use the debugger to find most run-time errors. Breakpoint before lines that you think would be causing a problem and try iterating through each line or just run the debugger and read the output (if that works for you). Pointers... not my forte. C++ and its containers are my reason for life.

Oh, and welcome to the forum.

EDIT:: Looking through the internet (google): I found something and changed your code to this

Code:
```static int comp(const void *a, const void *b) {
int *p1 = (int*)a;
int *p2 = (int*)b;
//
int diff1 = p1[0] - p2[0];
if (diff1) return diff1;
return p1[1] - p2[1];
}```
http://social.msdn.microsoft.com/For...-457b3b8fe305/

?

3. Thanks. I did try using various print statements and breakpoints to chase down the error before posting here. The array appears to initialize, but qsort passes a NULL pointer to argument 2 of the compare function which crashes the program.

EDIT::
Tried it with the suggested code change, but there is still something wrong with the pointer passed to argument 2 ( const void *b ). When you tell it to print the value of arr1[3] it obligingly does so, but when you tell it to print the value of arr2[3] it crashes again.

4. I just started looking at this code and I will post somethings that I see. First I noticed this:
Code:
```int **array = (int**)malloc(sizeof(int *) * 10);
for(i = 0; i <  10; i++){
array[i] = (int*)malloc(sizeof(int) * 4);
}```
You said that the number of rows is determined at runtime yet this code will actually produce a 10 x 4 array every time. I don't know if you meant to do this or not.

Also, when calling qsort you must use a function pointer which means that you should change your qsort call from:
Code:
`qsort(array, 10, sizeof(int) * 4, comp);`
to:
Code:
`qsort(array, 10, sizeof(array[0][0]), &comp);`
Note that the change of the sizeof statement is not necessary just makes it easier to look back and realize what you are trying to do. That should get you started.

5. Also, when calling qsort you must use a function pointer which means that you should change your qsort call from:
Code:
`qsort(array, 10, sizeof(int) * 4, comp);`
to:
Code:
`qsort(array, 10, sizeof(array[0][0]), &comp);`
Worked like a charm once I changed the qsort call. Thank you so much for taking the time to look at my code! Now to plug it back into the rest of the program.

6. I'm not clear on the current state of your code, but I don't think the changes suggested so far actually reliably fix your problem. There seems to be some confusion in this thread, so hopefully this will clear things up:

You declare array to be an int **. You allocate an array of int * (int pointers), that happen to point to arrays of ints. But your main array is still just an array of int pointers (each element is a pointer to an int). You don't have a true 2-d array, and you aren't truly swapping rows, just the pointers to the rows. Thus, your call to qsort should look like this:
Code:
`qsort(array, 10, sizeof(array[0]), comp);`
Your version was definitely wrong, it said that each element was the size of 4 ints. That implies your main array is far bigger than it actually is. You were running off the end of the array, hence the seg fault. The change suggested by breimer273 worked out of sheer luck. array[0][0] is an int, which commonly has the same size as an int *, but may not. It is not safe. The best thing to do for the size of an element is take the array of things you want to sort (array), and add a * in front, or add one set of brackets after it only, with a number in it.

As a note, the presence of lack of an & when trying to get a function pointer is irrelevant. The name of the function alone, with no parentheses, serves as a pointer to the function. Some people like to see it, others don't, it doesn't really matter.

Now, back to the qsort issues. When qsort calls your compare function, it passes pointers to the two elements in your array to compare. Since you have an array of int pointers, your comp function gets passed pointers to int pointers, i.e. int **. That is easy to forget, and any warning is gone because they are passed in as void * and it's your responsibility to properly cast them back to what they are. If you cast them as Rodaxoleaux suggests, you're ignoring one level of indirection, i.e. one *. Those int ** themselves aren't arrays (even if you cast them to an int *), thus you can't do arr1[3], they merely point to arrays. You need to dereference them before accessing elements [2] and [3]. Like this:
Code:
```int comp(const void *a, const void *b)
{
int *arr1 = *((int **) a);
int *arr2 = *((int **) b);

int diff1 = arr1[3] - arr2[3];
if (diff1) return diff1;
return arr1[2] - arr2[2];
}```
Those two changes should fix your problems.

7. That absolutely did the trick and thank you for the great explanation. I am posting the final code in case some other wayward soul with qsort problems stumbles across this thread.

Code:
```#include <stdio.h>
#include <stdlib.h>

/* QSORT COMPARE FUNCTION - SORTS BY COLUMN 4
DESCENDING AND THEN BY COLUMN 3 ASCENDING */
int comp(const void *a, const void *b)
{
int *arr1 = *((int **) a);
int *arr2 = *((int **) b);

int diff1 = arr2[3] - arr1[3];
if (diff1) return diff1;
return arr1[2] - arr2[2];
}

/* MAIN */
int main(void)
{

int rows = 10;
int cols = 4;
int i;

/* INITIALIZE DYNAMIC 2D INTEGER ARRAY */
int **array = (int**)malloc(sizeof(int *) * rows);
for(i = 0; i <  rows; i++)
{
array[i] = (int*)malloc(sizeof(int) * cols);
}

/* FILL ARRAY WITH DUMMY INTEGER VALUES */
for(i = 0; i < rows; i++)
{
array[i][0] = i ;
array[i][1] = i * 2;
array[i][2] = rand() % 2;
array[i][3] = rand() % 10;
}

/* SORT ARRAY */
qsort(array, rows, sizeof(array[0]), comp);

/* FREE DYNAMICALLY ALLOCATED MEMORY*/
for(i = 0; i < rows; i++)
{
free(array[i]);
}
free(array);

return 0;
}```