qsort on array of pointer to structure

[logicalguy]

Hi, I have a qsort problem I just can't solve.

I've got an array of pointers to a structure called struct mys. The structure has an int value called id. I want to use qsort to sort this array of pointers to structure in ascending order by the id value in each of the structures referenced. Hope I'm making sense. Here is the code I've tried:

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

struct mys  {
    int id;
    int size;
};

int indirectstructsortbyid(const void *i1, const void *i2)  {
    struct mys *a = (struct mys *)i1;
    struct mys *b = (struct mys *)i2;

    return (a->id - b->id);
}

void sort_indirect_structs()  {
    struct mys master[] = { {11, 11}, {33, 33}, {55, 55}, {77, 77}, {99, 99},
                            {22, 22}, {44, 44}, {66, 66}, {88, 88}
                        };
    struct mys **mboo;
    int count = sizeof(master) / sizeof(struct mys);

    mboo = malloc (sizeof(struct mys*) * count);

    int i;
    for (i = 0; i < count; i++)  {
        *(mboo+i) = &master[i];
    }

    printf("\nbefore qsort\n");
    for (i = 0; i < count; i++)  {
        printf("%d: id = %d, size = %d\n", (i+1), (**(mboo+i)).id, (**(mboo+i)).size);
    }

    qsort(mboo, count, sizeof(struct mys*), indirectstructsortbyid);

    printf("\nafter qsort\n");
    for (i = 0; i < count; i++)  {
        printf("%d: id = %d, size = %d\n", (i+1), (**(mboo+i)).id, (**(mboo+i)).size);
    }
    free(mboo);
}

int main()
{
    sort_indirect_structs();
    return 0;
}

Thanks for your help...

[Adak]

Change the return from your compare function to:

return(*(int*)a->id - *(int*)b->id);

And it works fine. Nice program, btw.

That GD casting on the return from the compare function, is one reason I dislike C's qsort. Sure, it's nice for different kinds of data, but damn it, people sort two things, a great deal - strings and numbers.

It doesn't have to be that much of a PITA. (By itself, Quicksort doesn't need this kind of bull ----).

[Ancient Dragon]

The comparison function is comparing addresses, not the values that are in the structures

int indirectstructsortbyid(const void *i1, const void *i2)  {
    struct mys **a = (struct mys **)i1;
    struct mys **b = (struct mys **)i2;
    return (*b)->id - (*a)->id;
}

[edit]^^ Adak beat me to it.[/edit]

[logicalguy]

Thanks, both of the above solutions worked great :)

I will have to give the pointer manipulation bits a think, though, before I'm convinced I've understood it.

Thanks again.

[Dave Sinkula]

That GD casting on the return from the compare function, is one reason I dislike C's qsort. Sure, it's nice for different kinds of data, but damn it, people sort two things, a great deal - strings and numbers.

It doesn't have to be that much of a PITA. (By itself, Quicksort doesn't need this kind of bull ----).

There is no need for any casting. In fact, I am more comfortable that the compare function is written correctly if no casts are present. And the subtraction is subject to signed integer overflow.

[Adak]

It wants constant void pointers, so you have to cast from what I've seen. .

I have 4 versions of Quicksort, and none of them need casting like the qsort() version.

I'd like to see some qsort examples that eliminate casting to and from the call to qsort, and it's compare function.

When you want to sort strings, the first thing you do is cast the string array to type void *:

qsort((void *) strArray, . . .

Then the compare function has to cast the sub array range, to constant void *, for both low and hi, as well.

[Dave Sinkula]

It wants constant void pointers, so you have to cast from what I've seen.

Void pointers do not need explicit casts to other (object) pointer types in C.

I'd like to see some qsort examples that eliminate casting to and from the call to qsort, and it's compare function.

Sure:

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

struct T
{
   int id;
   int size;
};

int indirec_by_id(const void *a, const void *b)  
{
   const struct T *const *x = a;
   const struct T *const *y = b;
   if ( (*x)->id > (*y)->id ) return 1;
   if ( (*x)->id < (*y)->id ) return -1;
   return 0;
}

void show(const struct T *m, struct T **p, size_t size)
{
   size_t i;
   for ( i = 0; i < size; ++i )
   {
      printf("data[%lu]: id = %d, size = %d; "
             "addr[%lu]: id = %d, size = %d\n", 
             (long unsigned)i, m[i].id,  m[i].size, 
             (long unsigned)i, p[i]->id, p[i]->size);
   }
}

int main()
{
   struct T data[] = 
   { 
      {11, 11}, {33, 33}, {55, 55}, {77, 77}, {99, 99},
      {22, 22}, {44, 44}, {66, 66}, {88, 88},
   };
   size_t i, count = sizeof data / sizeof *data;
   struct T **addr = malloc (count * sizeof *addr);

   for ( i = 0; i < count; i++ )
   {
      addr[i] = &data[i];
   }

   puts("Before:");
   show(data, addr, count);

   qsort(addr, count, sizeof *addr, indirec_by_id);

   puts("After:");
   show(data, addr, count);

   free(addr);
   return 0;
}

When you want to sort strings, the first thing you do is cast the string array to type void *:

I don't. As I said, I prefer to avoid casting altogether.