How to qsort an array of pointers that use structs?

Question

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
.
.
.

Community · Accepted Answer · 2017-05-23 12:24:33Z

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

edited May 23, 2017 at 12:24

CommunityBot

11 silver badge

answered Dec 4, 2016 at 19:19

Jonathan Leffler

760k145 gold badges961 silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Cero Over a year ago

I've added your corrections, however the program crashes when qsort is called.

Jonathan Leffler Over a year ago

We can't see how you populate your database * structure; that makes it hard for us to guess whether you've got something wrong in that code, or whether there's a problem in what I wrote.

Cero Over a year ago

Do u mean how the database is initialized or how entries are inserted? Anyways I've posted both.

Jonathan Leffler Over a year ago

Well, see my version of an MCVE (minimal reproducible example) in my answer. Basically, your question should include an compilable but minimal program that reproduces your problem. It is not clear how all the fragments of code in your question are linked together. Note that one key step in my MCVE is printing the data before the sort. That ensures that the data itself is valid according to the printing function — if it produces gibberish, you know that the sort isn't going to be able to fix it.

Jonathan Leffler Over a year ago

Incidentally, your insertE() function simply leaks memory. You need to return the allocated block * and stash it somewhere appropriate (the array of block pointers, presumably). If you are using that to record your data, then therein lies another of your problems — presumably why you were testing for null pointers in the array before printing the ID values. Congratulations on implementing the allocation for the name correctly — not everyone remembers the terminal null, but you did. The problems here show why it is important to test in stages — test that you can print what you've read.

|

Some programmer dude · Accepted Answer · 2016-12-04 19:02:06Z

0

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

answered Dec 4, 2016 at 19:02

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

3 Comments

Cero Over a year ago

When I check to see if the array of pointers is sorted the output of the ids shows that they are not sorted. If that makes any sense.

Some programmer dude Over a year ago

@Cero By not passing the correct element size, you actually have undefined behavior. Anything could happen.

nos Over a year ago

There's another issue, in that the compare function will be passed a pointer to the elements. And since the elements themselves are pointers, you'll have to do e.g. const block **eval1 = a;

Collectives™ on Stack Overflow

How to qsort an array of pointers that use structs?

2 Answers 2

MCVE

Example output:

7 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

MCVE

Example output:

7 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related