C qsort() with dynamic n by 2 multi-dimensional array

Question

First, I defined a dynamic array with 2 columns and 10 row. The integer number is set to 10 here just for example.

int** array;
int number = 10;

array = malloc(number * sizeof(int*));

for (i = 0; i < number; i++)
    array[i] = malloc(2 * sizeof(int));

Then I try to use qsort() on it.

qsort( array, number, sizeof array[0], compare );

This is my compare function. It sorts by the integer values in the first column, then sorts by the second column while preserving the order in the first column. E.g. "0 2, 1 7, 0 1" will become "0 1, 0 2, 1 7".

int compare ( const void *pa, const void *pb ) {
    int (*a)[1] = pa;
    int (*b)[1] = pb;
    if ( (a[0][0] < b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] < b[1][0]) ) return -1;
    if ( (a[0][0] > b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] > b[1][0]) ) return +1;
    return 0;
}

Question

This worked with a static array. I know it doesn't work now because I have a dynamic array, which is an array of pointers.

How can I adapt this code to work with the dynamically created multi-dimensional array?

Spiegelman

Pointer-to-array != pointer-to-pointer. – Dorpat

Answer 1

sample code

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

int compare ( const void *pa, const void *pb ) {
    const int *a = *(const int **)pa;
    const int *b = *(const int **)pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}
/*
#define NUMCMP(x,y) (((x) < (y)) ? -1 : ((x) > (y)) ? 1 : 0)

int compare ( const void *pa, const void *pb ) {
    const int (*a)[2] = *(const int (**)[2])pa;
    const int (*b)[2] = *(const int (**)[2])pb;
    int tmp;
    if((tmp=NUMCMP((*a)[0], (*b)[0]))==0)
        return NUMCMP((*a)[1], (*b)[1]);
    else
        return tmp;
}
*/    
int main(void){
    int **array;
    int number = 10;
    int i;

    array = malloc(number * sizeof(int*));
    for (i = 0; i < number; i++){
        array[i] = malloc(2 * sizeof(int));
        array[i][0] = rand()%20;
        array[i][1] = rand()%20;
    }
    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    printf("\n");

    qsort(array, number, sizeof array[0], compare);

    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    return 0;
}

what *(const int **)pa

array = {(int *), (int *), (int *), ... , (int *) }

qsort need each element address for element (for swap, etc. Because the size and number and start address of the element since only the given information).

E.g &(int *), &(int *)

so (int **) pass to function compare.

call compare(int **, int **) &(int*) meant at arg int**

compare function prototypeis cmp(const void*, const void*)

cast (const int**)pa is cast to passed original pointer.

*((const int **)pa) is dereference original element pointer(int*)

Sayres

Note that return a[1] - b[1]; (and similar expressions) is dangerous if the value in a is large and positive and the value in b is large and negative (or vice versa). You can get arithmetic overflow, which leads to undefined behaviour. For most reasonable data sets, this will not be a problem. However, you should be aware of the issue. – Arms

@JonathanLeffler goot point, thanks. but note that in this case 0 or more value each is value of rand. – Sayres

I am interested in second solution whre you did: const int (*a)[2] = *(const int (**)[2])pa; const int (*b)[2] = *(const int (**)[2])pb; which is quite confusing. Could you explain it that how this is valid because AFAIK, string is of type int ** here and hence pa and pb should be of type int **. Am I missing something? – Polar

@haccks, hint : array[i] = malloc(2 * sizeof(int)); – Sayres

@BLUEPIXY; Yes. I understand what you are saying, but here array is of int ** type and hence array[i] is of int *. Allocating memory to array[i] = malloc(2 * sizeof(int)); doesn't make it int (*)[2] type, it is still int * type. – Polar

@Polar , small sample code : In a sample, receives a pointer to the same address as a:int* (or &a:int(*)[2]) in the comparison function. It can be interpreted by either casting it. – Sayres

OK. You mean here we are seeing the address of elements instead of pointer type ? – Polar

@Polar , I do not know well the meaning of the your question, After all, It only has been cast in the pointer you want to interpret it is received by the void * a pointer to the address of memory of size of the 2 int. – Sayres

OK. One question at one time :). Tell me the type of array ? – Polar

@Polar int **array; – Sayres

OK. If I will pass it to qsort then what would be the type of p and q in compare function? – Polar

@Polar , E.g int *p1 = malloc(2*sizeof(int)); int (*p2)[2] = malloc(2*sizeof(int)); --> func((void*)&p1) <-> func((void*)&p2) : Are both the same as a pointer to another type for func. It can be interpreted either way. – Sayres

No. I am asking about type of pointer passed to compare function when int ** type is passed to qsort. By the way do you mean func((void*)&p2) ----> func((void*)p2) ? (I know because of your poor English you are finding it hard to explain but I hope you will do :) ) – Polar

@Polar , int compare ( const void *pa, const void *pb ) ; be treated in the qsort function Remember that it is a pointer to an object. – Sayres

I read that, base pointer in qsort must point to the first element in the array and pa, pb should be the pointers to array elements. That means, pointer passed to pa and pb is of type int ** because array is of type int **, am I wrong? – Polar

@Polar , It will receive as a void * instead of int ** The comparison function. type of pb and pa is only void * instead of int **. – Sayres

Oh! Good. That mean you only need to cast pa and pb to pointer to elements of array, right? – Polar

@Polar yes, There is no difference are you trying to operate after all only an address of 2 int. – Sayres

Yes. Finally we need to operate on array of int[2]. So it can be done in either ways: const int *a = *(const int **)pa; const int *b = *(const int **)pb; or const int (*a)[2] = *(const int (**)[2])pa; const int (*b)[2] = *(const int (**)[2])pb;. Got it!. But is this also valid: const int (*a)[2] = (const int (*)[2])pa; const int (*b)[2] = (const int (*)[2])pb; ? – Polar

@Polar , valid? : no, because call like this func((void*)&p2), it is int (**)[2]. – Sayres

You mean pa, pb can't be casted to (const int (*)[2]) in this case ? – Polar

Why? I do not understand what you said in previous comment : because call like this func((void*)&p2), it is int (**)[2]...... What is func((void*)&p2) here? – Polar

@Polar p2 type is int (*)[2]. pointer to p2 (&p2) type is int (**)[2]. – Sayres

Yes . I know. Did you mean by func((void*)&p2) function call of compare in qsort ? – Polar

@Polar This is the same as the meaning. – Sayres

@Polar Why ask a question like that at this late hour? Why do you understand and accept int(*)[2] if that even though it has already been understood to be received by the int ** when int * is operated as an element is received is int(*)[2](Pointer is as it is this.) Are you ? – Sayres

@BLUEPIXY; Because currently I am working on qsort that's why I am asking it to you :) (sorry for the inconvenience). – Polar

you are welcome. It works in the array with the elements int *. – Sayres

say again, "pointer to an object." , case of int* --> int**. case of int (*)[2] to int (**)[2]. – Sayres

Well I am confused because I do not understand how both of const int *a = *(const int **)pa; and const int (*a)[2] = *(const int (**)[2])pa; works. I think I do not actually understand how qsort call compare function. Thanks for your effort. I am awarding you a bounty of worth 100 reputation for your help and effort. :) – Polar

I think good to try and implement the qsort for understanding. – Sayres

I implemented in lots of code but still wondering how compare function worked in some cases. – Polar

@Polar Do you want to hear about it (the part that is commented out) ? – Sayres

1) return strcmp(pp, qq); in comp_string : this is wrong. – Sayres

2)return strcmp(pp, qq); in comp_string_array_2D : this is OK. – Sayres

But return strcmp(pp, qq); is working in comp_string as well. – Polar

no , you miss read. case 1) pointer to pointer to address of memory of array of char. strcmp need address of memory, not pointer (address). E.g P -> "string", strcmp need "string", not p(void* is &p). – Sayres

Case 1) is wrong for both of ptr_to_ptr and array_of_ptr function? – Polar

case 2) void* is "string", not &P. So strcmp can be applied as it . – Sayres

But I think the function call made by qsort is something like comp_string_array_2D((void *)(*)[10], (void*)(*)[10]) so p and q are address of "strings" instead of "string". – Polar

remember small sample code. real 2D array layout [[1st 10][2nd 10][3rd 10]]. pointer to treat in qsort is a pointer to the elements of each.(E.g. [1st 10]) It is a string(char [10]) in this case. – Sayres

Let us continue this discussion in chat. – Polar

Could you tell me please the reason for the warning in this question. I tried it using casting and it worked. const int (*a)[2] = (int (*)[2])pa; – Polar

@Polar , case of const int (*a)[2] = pa; : I think to be a possibly excessive warning. case of const int (*a)[2] = (int (*)[2])pa; : Warning in this case is reasonable. because It is gone in the const. – Sayres

Sorry, I mean const int (*a)[2] = (const int (*)[2])pa; worked. – Polar

@Polar I think that it's become such warnings when trying to assign the result has been translated to a (void *) automatically once perhaps the case of gcc. It does not occur with clang. – Sayres

Answer 2

Since you now have an array of pointers, the arguments to your comparison function are going to be pointers to pointers. Use them like this:

int *const *a = pa;
int *const *b = pb;

Now you have a and b as two pointers into the array you're sorting. Each one points to a single element that the sort function is asking you to examine. You can access these elements as *a and *b or a[0] and b[0] but should not ever use a[1] or b[1]. If the sort function asks you to compare the first element in the array (*a) and the fifth element in the array (*b), a[1] and b[1] are the second and sixth elements of the array - completely irrelevant to the comparison you're supposed to be doing.

After the first level of dereferencing, you're allowed to do whatever you need to do to examine the elements being compared. Since your array elements are themselves pointers to arrays (of 2 int each), the ints can be accessed as a[0][0] a[0][1] b[0][0] b[0][1]. Notice this is the opposite order from your a[1][0] and b[1][0].

Writing them as (*a)[0] would provide a reminder that the first level of indirection is a "single-element-access-only" pointer. I'm undecided on whether this makes the whole thing clearer.

Housel

Answer 3

I came across this thread in search of a ditto problem of mine, and I lastly end-up doing the below thing.

static int compareMatrixElements(const void *p1, const void *p2)
{
    return ((*(int const *) p1) - (*(int const *) p2));
}

void sortMatrix(int** matrix, int r, int c)
{
    int sort_matrix[r][c];

    for(int i = 0; i < r; i++) {

        memcpy(sort_matrix[i], matrix[i], c * sizeof(int));
    }

    qsort(sort_matrix, r*c, sizeof(int), compareMatrixElements);

    for(int i = 0; i < r; i++) {

        memcpy(matrix[i], sort_matrix[i], c * sizeof(int));
    }
}

In the above code of mine I used qsort API directly, one can use this api or any other sort algo on a contiguous memory, but what If you are having a matrix whose rows are pointer to the memory of its columns (like in my case as well as described in the question of this thread). Hence I copied such matrix into a contiguous memory, ran sort on that contiguous memory and copied back the sorted elements to the matrix.

The above solution worked for me, I thought it might be helpful others so I posted it, suggest any improvement for the same.

Action

Answer 4

const int *a = *(const int **)pa;
const int *b = *(const int **)pb;

@BLUEPIXY, this is not correct. Just enough

const int *a = pa;
const int *b = pb;

becouse pa is const void * (array[0]) and it very well cast to const int *

Bicameral

Answer 5

const int (*a)[2] = *(const int (**)[2])pa;
const int (*b)[2] = *(const int (**)[2])pb;

@BLUEPIXY, this is not correct. Just enough

const int (*a)[2] = (int(*)[])pa;
const int (*b)[2] = (int(*)[])pb;

Bicameral

Answer 6

sizeof array[0] will be "2 * sizeof(int)", for this static array.

int array[10][2];

sizeof array[0] will be "sizeof(int*)", for this pointer-to-pointer. sizeof array[0][0] will be "sizeof(int)", for this pointer-to-pointer.

int **array;

So, First thing is you cannot use "qsort( array, number, sizeof array[0], compare );" in case of pointer-to-pointer implementation.

Reluct