How to sort 2D dynamic array of structs

Question

I am having trouble sorting a 2D dynamic struct array.

I have a struct:

typedef struct abc
{
    int total;
} abc;

And a dynamic 2D array:

list = (abc**)malloc(listSize * sizeof(abc*));
    for (int i = 0; i < listSize; i++)
    {
        list[i] = (abc*)malloc(listSize2* sizeof(abc));
    }

I want to use a sorting algorithm:

qsort(list, listSize, sizeof list[0], cmp);

and the compare function for the qsort:

int cmp(const void *l, const void *r)
{
    const abc *a = *(const abc **)l;
    const abc *b = *(const abc **)r;

    return a[0].total > b[0].total;

}

But the problem is that although I think it works for a small list (like about 5 ints), it fails to sort properly if the list is a bit bigger. What should I do to the cmp() function so it works properly?

By the way, I only need to sort list[x][0] since I will be adding more elements later.

(I'm basing my sorting code from another Stackoverflow post)

Ivaylo Strandjev · Accepted Answer · 2013-09-27T09:14:56.653

5

Change the compare function to:

int cmp(const void *l, const void *r)
{
    const abc *a = *(const abc **)l;
    const abc *b = *(const abc **)r;

    return a[0].total - b[0].total;

}

Using qsort the expected compare function should return negative if first value is smaller positive if it is bigger and 0 if the two values are equal.

EDIT: thanks to WhozCraig: if you think you may hit under or overflow you may go for a safer version:

int cmp(const void *l, const void *r)
{
    const abc *a = *(const abc **)l;
    const abc *b = *(const abc **)r;

    if (a[0].total < b[0].total) {
       return -1;
    } else if (a[0].total > b[0].total) {
       return 1;
    } else {
       return 0;
    }
}

edited Sep 27 '13 at 09:14

answered Sep 27 '13 at 09:01

Ivaylo Strandjev

69,226
18
123
176

1

The only thing problematic with this is if `a[0].total` is already a negative number and `b[0].total is a very large *positive* number. The subtraction method is subject to underflow (or overflow if the signs are reversed). – WhozCraig Sep 27 '13 at 09:11
1

Yeah, that would do it. You can also get away with `return (a < b) ? -1 : (b < a);`. (oh, and +1) – WhozCraig Sep 27 '13 at 09:18
The first one gives me a Segmentation Fault but the second one works! Thanks everyone! – StarShire Sep 27 '13 at 09:33

LihO · Answer 2 · 2013-09-27T09:27:03.803

2

With the following structure:

typedef struct abc {
    int total;
} ABC;

Compare function can be simple as:

int cmp(const void *l, const void *r)
{
    const ABC *a = (const ABC *) l;
    const ABC *b = (const ABC *) r;
    if (a->total == b->total) return 0;
    return (a->total < b->total) ? -1 : 1;
}

used for example like:

ABC list[][4]  = {{{5},{2},{0},{4}},
                  {{7},{3},{9},{1}},
                  {{8},{6},{5},{7}},
                  {{2},{7},{9},{5}}};

qsort(list, 4 * 4, sizeof(ABC), cmp);

for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j)
        printf("%d ",list[i][j].total);

which outputs: 0 1 2 2 3 4 5 5 5 6 7 7 7 8 9 9.

And in case you want to sort it within rows only, you could do:

for (int i = 0; i < 4; ++i)                 
    qsort(list[i], 4, sizeof(ABC), cmp);

which would give you: 0 2 4 5 1 3 7 9 5 6 7 8 2 5 7 9. In this case (sorting within rows), it doesn't matter whether the list as whole is stored within the single block of memory or not. Neither it matters if it has been allocated dynamically or not :)

edited Sep 27 '13 at 09:27

answered Sep 27 '13 at 08:46

LihO

41,190
11
99
167

in c's qsort the compare function is not boolean it returns a negtive value, positive value or 0. – Ivaylo Strandjev Sep 27 '13 at 08:59
@IvayloStrandjev: Yes. Thanks, I fixed it. Although the previous version somehow worked too. – LihO Sep 27 '13 at 09:04
@LihO I saw your code before you edited after Ivaylo Strandjev's comment and the code did attempt to sort it but the list was still a mess. The code after the edit doesn't seem to work for some reason. Gives me a Segmentation Fault. – StarShire Sep 27 '13 at 09:33
@StarShire: I had there one more typo while sorting within rows, I was passing `list[0]` instead of `list[i]`, you might check edit log. – LihO Sep 27 '13 at 09:34

How to sort 2D dynamic array of structs

2 Answers2