Как быстро отсортировать массив указателей на структуры в C?

Question

Итак, есть много примеров использования qsort() со структурами, указателями и т. Д. Но ни один из них, похоже, не правильно сортируется в моей реализации.

Это обзор моего кода:

#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; 
} 

Этот код, чтобы продемонстрировать свою проблему, поэтому, пожалуйста, не напыщенная речь на меня семантику! Дополнительное неиспользуемое пространство в массиве является преднамеренным. : p

Насколько я знаю и от того, что я читаю в Интернете, это должно работать. Но это не так. По какой-то причине он начинает сортировку по значениям мусора в функции сравнения.

Я требую, чтобы массив часто был больше значений внутри него, поэтому надеялся, что второй аргумент функции qsort() ограничит его только первыми тремя элементами в этом случае. Но, похоже, это игнорирует это.

Любые идеи, что вызывает это странное поведение?

Answer 1

Joachim has solved one problem, есть другой. qsort передает указатели на элементы массива до compare, даже если они уже указатели. Таким образом, compare получает Node **, двойной указатель. Вы можете увидеть это, если вы напечатаете node->value внутри compare.

Соответствует.

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

Answer 2

Когда вы передаете *myArray в качестве первого аргумента функции qsort, это как прохождение myArray[0], который, безусловно, не правильный указатель (и приведет к непредсказуемому поведению и, скорее всего, какой-то странное поведение как сортировка данных «мусора»).

Либо пусть матрица распадается на указатель на первый элемент, используя простой myArray или явно указывая первый элемент, используя &myArray[0].