How to qsort an array of pointers that use structs

I want to sort an array of pointers by Id's. However qsort fails to work because of my lack of experience with pointers.

typedef struct block{
    int Id;
    char * name;
} block;

typedef struct {
    block ** data;
    int size_array;
} database;

if( ( database = malloc(sizeof(database)) ) == NULL ) {
    printf("Error: malloc failed\n");
    exit(EXIT_FAILURE);
}

if( ( database->data = malloc( sizeof( block * ) * database->size_array ) ) == NULL ) {
    exit(EXIT_FAILURE);
}

for( i = 0; i < database->size_array; i++ ) {
    DB->data[i] = NULL;
}

I'm trying to sort using qsort, but I'm clearly doing something wrong.

int compare(const void * a, const void * b ){
    const block * eval1 = a;
    const block * eval2 = b;

    if (eval1->Id < eval2->Id){
        return(-1);
    }

    else if (eval1->Id > eval2->Id)
        return 1;

    return 0;
}

Calling code:

    qsort(database->data, database->size_array, sizeof(int), compare);
    for(i = 0; i<DB->database->size_array; i++) {
        if(database->data[i] != NULL)
            printf("Id: %d\n", database->data[i]->Id);

    }

By using a for loop I see that the sorting failed.

Insert Function:

void insertE(int Id, char * name){
    block * item = malloc(sizeof(block));
    item->name = malloc(strlen(name)+1);
    strcpy(item->name, name);
    item->Id = Id;
}

current output:

Id: 13
Id: 243
Id: 121
Id: 87
.
.
.

回答1:

When you use qsort() (or bsearch() or other similar functions), the pointers passed to your comparison function are of the type 'pointer to the array element type'. If you pass an array of int, the comparison function is passed int * (disguised as void *). Consequently, if you have an array of block *, the type passed to the comparator is a block ** (disguised as a void *).

Hence you need something like this (though there are other ways to write it too):

int compare(const void *a, const void *b)
{
    const block *eval1 = *(block **)a;
    const block *eval2 = *(block **)b;

    if (eval1->Id < eval2->Id)
        return(-1);
    else if (eval1->Id > eval2->Id)
        return 1;
    return 0;
}

However, there are other problems too. Your call to qsort is suspect; the size of the array elements is sizeof(db->data[0]) (assuming db is a variable of type database *), which is also sizeof(block *). In general, on 64-bit Unix and Windows systems in particular, sizeof(int) != sizeof(block *). You will get away with using sizeof(int) on platforms where sizeof(int) == sizeof(void *), a category which include most 32-bit systems. Therefore, you need to fix the call to qsort() too:

database *db = …initialization/allocation…;

qsort(db->data, db->size_array, sizeof(db->data[0]), compare);

MCVE

Any residual problems are most probably related to how the array of block pointers is populated. Here is an MCVE (Minimal, Complete, Verifiable Example) that shows the sort working on an array of block pointers. It assumes you have a C99 or C11 compiler available — it uses 'compound literals' which were not in C90.

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

typedef struct block
{
    int Id;
    char *name;
} block;

typedef struct
{
    block **data;
    int size_array;
} database;

static int compare(const void *a, const void *b)
{
    const block *eval1 = *(block **)a;
    const block *eval2 = *(block **)b;

    if (eval1->Id < eval2->Id)
        return(-1);
    else if (eval1->Id > eval2->Id)
        return 1;
    return 0;
}

static void dump_blocks(const char *tag, int nblocks, block * *blocks)
{
    printf("%s:\n", tag);
    for (int i = 0; i < nblocks; i++)
        printf("Id: %3d - %s\n", blocks[i]->Id, blocks[i]->name);
    putchar('\n');
}

int main(void)
{
    block *b[] =
    {
        &(block){232, "RDQDLY"     },
        &(block){347, "XRZDMGJAZ"  },
        &(block){827, "QBYCVGQ"    },
        &(block){790, "VXSPDUX"    },
        &(block){245, "QRZEGGKAHD" },
        &(block){717, "YGKRPIGFM"  },
        &(block){691, "SREIUBHVS"  },
        &(block){754, "ZCFLESX"    },
        &(block){868, "WESFFWMJ"   },
        &(block){291, "QCSAGIHQJ"  },
    };
    database *db = &(database){ &b[0], sizeof(b) / sizeof(b[0]) };

    dump_blocks("Before sort", db->size_array, db->data);
    qsort(db->data, db->size_array, sizeof(db->data[0]), compare);
    dump_blocks("After sort", db->size_array, db->data);

    return 0;
}

The dump_blocks() function follows a pattern I find very useful: the function takes a string tag that is printed first to identify which set of output is being dumped, and then prints all the relevant information from the data structure (using other dump_xxxxx() functions if appropriate). This can then be called in multiple places. If need be, I provide a FILE *fp output stream as a first argument; it didn't seem to be necessary here. It can also use fflush(fp); or fflush(stdout); or perhaps fflush(0); at the end of the function to ensure that the output is produced. This can help when debugging a program that's crashing. Note that the outputs are terminated with a newline to help ensure they appear in a timely manner.

Example output:

Before sort:
Id: 232 - RDQDLY
Id: 347 - XRZDMGJAZ
Id: 827 - QBYCVGQ
Id: 790 - VXSPDUX
Id: 245 - QRZEGGKAHD
Id: 717 - YGKRPIGFM
Id: 691 - SREIUBHVS
Id: 754 - ZCFLESX
Id: 868 - WESFFWMJ
Id: 291 - QCSAGIHQJ

After sort:
Id: 232 - RDQDLY
Id: 245 - QRZEGGKAHD
Id: 291 - QCSAGIHQJ
Id: 347 - XRZDMGJAZ
Id: 691 - SREIUBHVS
Id: 717 - YGKRPIGFM
Id: 754 - ZCFLESX
Id: 790 - VXSPDUX
Id: 827 - QBYCVGQ
Id: 868 - WESFFWMJ

回答2:

You have an array of pointers to block, not an array of int. The sizeof argument is the size of the elements in the array, not the size of the data you want to compare.

So the correct call would be e.g.

qsort(database->data, database->size_array, sizeof *database->data, compare);