qsort not properly sorting array of pointers to struct in C

Question

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 :)

Yeah it is. It's sorted in descending order of value. Big ones come before smaller ones. Reverse the return 1 and return -1 in your compare func to sort in ascending order. ;) — enhzflep
– enhzflep, Commented Jul 11, 2021 at 12:28
@enhzflep it's not. the order descending u see is given by the definition of the test case I have used if u swap the returns the output is the same. sry for the misleading testcase :) — MrCont
– MrCont, Commented Jul 11, 2021 at 12:31
9999, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21 - You tell me then. Which one's out of order?! What was the initial order? — enhzflep
– enhzflep, Commented Jul 11, 2021 at 12:36

Vlad from Moscow · Accepted Answer · 2021-07-11 12:38:52Z

2

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

answered Jul 11, 2021 at 12:38

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MrCont Over a year ago

Thank you, that solved my problem :) may I ask u why (Node*)a doesn't work while *(Node**)a does?

Vlad from Moscow Over a year ago

@MrCont Elements of your array have the pointer type Node *. They are passed to the comparison function by reference that is like for example &box[i]. So the type of the passed to the function expression is Node * *.

Collectives™ on Stack Overflow

qsort not properly sorting array of pointers to struct in C

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related