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

Legendre picture Legendre · Jun 20, 2013 · Viewed 13.6k times · Source

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?

Answer

BLUEPIXY picture BLUEPIXY · Jun 20, 2013

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*)