qsort not properly sorting array of pointers to struct in C

user_12579434 0
Viewed 48

I am trying to use qsort to sort an array of pointers to struct by one of the values.

Any help would be appreciated as I can't figure out why this doesn't work. the compare function seems right to me, I am wondering if something is wrong with unsigned ints.

the struct:

typedef struct node{

    unsigned int identifier;
    unsigned int value;

}Node;

the compare function:

int compare(const void* a, const void* b){
    
    Node* sum_a = (Node*)a;
    Node* sum_b = (Node*)b;
    if(sum_a->value > sum_b->value)return 1;
    if(sum_a->value == sum_b->value)return 0;
    return -1;
}

the code I have used to reproduce the problem:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define SIZE 20
Node* init_node(Node* ins_node,unsigned int identifier,unsigned int value){
    ins_node = (Node*)malloc(sizeof(Node));
    ins_node->identifier=identifier;
    ins_node->value=value;
    return ins_node;
}
int main (){

    Node*curr_node;
    Node*box[SIZE];
    box[0]=init_node(curr_node,27,9999);
    for(int i = 1;i<SIZE;i++){
        box[i]=init_node(curr_node,i,SIZE*2-i);
    }

    qsort(box,SIZE,sizeof(Node*),compare);

    printf("\nsorted:\n");
    for(int i = 0;i<SIZE;i++){
        printf("%d/%d\n",box[i]->identifier,box[i]->value);
    }
    
}

the output which is clearly not sorted:

sorted:
27/9999
1/39
2/38
3/37
4/36
5/35
6/34
7/33
8/32
9/31
10/30
11/29
12/28
13/27
14/26
15/25
16/24
17/23
18/22
19/21

Thanks to u all in advance :)

qsort pointers pass-by-reference sorting c
1 Answers

The comparison function is invalid and invokes undefined behavior. The elements of the array are passed by reference to the function. So you need to define the function at least like

int compare(const void* a, const void* b){
    
    Node* sum_a = *(Node**)a;
    Node* sum_b = *(Node**)b;
    if(sum_a->value > sum_b->value)return 1;
    if(sum_a->value == sum_b->value)return 0;
    return -1;
}

Also the first parameter of the function init_node is not used.

Define the function like

Node* init_node(unsigned int identifier,unsigned int value){
    Node *ins_node = (Node*)malloc(sizeof(Node));
    ins_node->identifier=identifier;
    ins_node->value=value;
    return ins_node;
}
user_28772410
Related