struct - sorting a c-string with qsort

Question

I'm sorting a bunch of IPs, but for some reason they come in the wrong order. I'm not quite sure where could be the problem.

66.249.71.3      
190.148.164.245  
207.46.232.182   
190.148.164.245  
190.148.164.245  
202.154.114.253
190.148.164.245  
190.148.164.245  
66.249.71.3      
190.148.164.245  
202.154.114.253

Here it is the way Im sorting them.

typedef struct {
    char *ip;
} mystruct;

/* qsort */
int struct_cmp(const void *a, const void *b)
{
    mystruct *ia = (mystruct *)a;
    mystruct *ib = (mystruct *)b;
    return strcmp(ia->ip, ib->ip);
} 
...
qsort(a_struct, 11, sizeof(mystruct*), struct_cmp);
for(..){
    printf("%s\n",a_struct[i]->ip);
}

Any help will be appreciate it. Thanks

Answer 1

You are sorting IP addresses as strings. This would actually work if they were normalized: instead of 66.249.71.3 you should have 066.249.071.003 if you want this to work.

I think your best bet is to use a function that converts a dotted IP address into a 32-bit integer, and then sort them using the resulting integers as the sorting key.

You should be able to use inet_addr() to do this conversion. Add this to your program:

#include <arpa/inet.h>

Documentation here.

Answer 2

You have an array of pointers to mystructs, but qsort with this comparision function would expect a simple array of mystructs. To sort an array of mystruct* you need to add another level of indirection to the comparison function:

int struct_cmp(const void *a, const void *b) {
    mystruct *ia = *(mystruct **)a;
    mystruct *ib = *(mystruct **)b;
    return strcmp(ia->ip, ib->ip);
}

Answer 3

There are at least two ways of fixing the sort code. One is to revise the comparator function to match the call to qsort(); the other is to fix the call to qsort() to match the comparator. The correct fix depends on the definition of the array - but the simplest declaration is an array of structures (not of structure pointers). Hence, this working code - which uses the original comparator but a different call to qsort():

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

typedef struct {
    char *ip;
} mystruct;

static mystruct a_struct[] =
{
    "66.249.71.3",
    "190.148.164.245",
    "207.46.232.182",
    "190.148.164.245",
    "190.148.164.245",
    "202.154.114.253",
    "190.148.164.245",
    "190.148.164.245",
    "66.249.71.3",
    "190.148.164.245",
    "202.154.114.253",
};

/* qsort */
static int struct_cmp(const void *a, const void *b)
{
    mystruct *ia = (mystruct *)a;
    mystruct *ib = (mystruct *)b;
    return strcmp(ia->ip, ib->ip);
}

static void print_list(mystruct *list, int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%2d: %s\n", i, list[i].ip);
}

#define DIM(x)  (sizeof(x)/sizeof(*(x)))

int main(void)
{
    print_list(a_struct, DIM(a_struct));
    qsort(a_struct, DIM(a_struct), sizeof(mystruct), struct_cmp);
    print_list(a_struct, DIM(a_struct));
}

This just leaves us with an alphanumerically sorted array of values, with all the '190.x.y.z' addresses appearing before the others, etc. Fixing that requires a more complex comparator - one solution for which is described by steveha in his answer.