How to quick sort an array of pointers to structures in C?

Question

So there are lots of examples of using qsort() with structures, pointers, etc. But none of them seem to sort correctly in my implementation.

This is an overview of my code:

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

struct node {
  int value;
};
typedef struct node Node;

int compare(const void *p1, const void *p2);

int main()
{
    Node *myArray[10];
    Node *node1, *node2, *node3;
    int i;

    node1 = (Node *)malloc(sizeof(Node));
    node1->value = 10;
    myArray[0] = node1;

    node2 = (Node *)malloc(sizeof(Node));
    node2->value = 7;
    myArray[1] = node2;

    node3 = (Node *)malloc(sizeof(Node));
    node3->value = 12;
    myArray[2] = node3;

    for (i=0; i<3; i++) {
        printf("Element %i: %i\n", i, myArray[i]->value);
    }

    printf("-------------\n");

    qsort(myArray, 3, sizeof(Node*), compare);

    for (i=0; i<3; i++) {
        printf("Element %i: %i\n", i, myArray[i]->value);
    }

    return 0;
}

int compare(const void *p1, const void *p2)
{
    Node *node1 = (Node*) p1;
    Node *node2 = (Node*) p2;

    return node1->value - node2->value;
}

This code is to demonstrate my issue, so please don't have a rant at me for semantics! The extra unused space in the array is intentional. :p

So as far as I'm aware, and from what I'm reading online, this should work. But it doesn't. For some reason it starts sorting through garbage values in the compare function.

I require the array to often be larger than the values within it, so hoped the second argument of the qsort() function would limit it to only the first 3 elements in this case. But it seems to be ignoring that.

Any ideas what's causing this strange behaviour?

I think p1 does not point at the node, but rather at the array element, i.e. the pointer to the node. You might need to doubly dereference p1 and p2. — Hermann Döppes, Dec 08 '15 at 19:57
Your code does not compile. `node->occurrences` is not defined and `main` is incomplete and `compare` is declared too late. And it should print the nodes at the end. Ultimately using `-` as a comparison operator makes no sense, but I can't tell if that's a bug or deliberate. Fix the code so it compiles and demonstrates the problem, please. — Schwern, Dec 08 '15 at 19:57
Possible duplicate of https://stackoverflow.com/questions/6167092/qsort-and-bsearch-an-array-of-pointers — Schwern, Dec 08 '15 at 20:15

score 3 · Answer 1 · answered Dec 08 '15 at 19:59

When you pass *myArray as the first argument to the qsort function, it's like passing myArray[0], which is definitely not the correct pointer (and will lead to undefined behavior and most likely some weird behavior like sorting "garbage" data).

Either let the array decay to a pointer to the first element by using plain myArray, or explicitly specify the first element using &myArray[0].

score 2 · Accepted Answer · edited May 23 '17 at 12:30

Joachim has solved one problem, there's another. qsort passes pointers to the array elements to compare even if they are already pointers. So compare is getting Node **, a double pointer. You can see this if you print node->value inside compare.

Cast accordingly.

static int compare(const void *p1, const void *p2)
{
    const Node *node1 = *(const Node **)p1;
    const Node *node2 = *(const Node **)p2;

    printf("cmp %d %d\n", node1->value, node2->value);
    return node1->value - node2->value;
}

How to quick sort an array of pointers to structures in C?

2 Answers2