qsort not sorting the content correctly, kruskal's algorithm

user_18455455 0
Viewed 48

I am trying to sort an array of structs using qsort, but it's not properly sorting the content. The structure node consists of the starting vertex, the ending vertex, and the cost of reaching from vertex 'a' to vertex 'b'.

I am writing the code for Kruskal's algorithm

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

int v, e;

typedef struct node {
    int a;
    int b;
    int cost;
} node;

int compare(const void *a, const void *b) {
    const node *x = *(node **)a;
    const node *y = *(node **)b;
    return (x->cost > y->cost) ? 1 : 0;
}

int main() {
    scanf("%d %d", &v, &e);
    int i;
    node *arr[e];
    for (i = 0; i < e; i++) {
        int a, b, cost;
        scanf("%d %d %d", &a, &b, &cost);
        arr[i] = (node *)malloc(sizeof(node));
        arr[i]->a = a;
        arr[i]->b = b;
        arr[i]->cost = cost;
    }
    qsort(arr, e, sizeof(node *), compare);
    printf("\n\n");
    for (int i = 0; i < e; i++) {
        printf("%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost);
    }
    return 0;
}

Input:

9 14
2 5 4
7 8 7
0 1 4
1 7 11
0 7 8
7 6 1
6 5 2
5 4 10
3 5 14
3 4 9
2 3 7
1 2 8
2 8 2
8 6 6

Output:

2 5 4
2 8 2
0 1 4
8 6 6
6 5 2
7 6 1
7 8 7
2 3 7
1 2 8
0 7 8
3 4 9
5 4 10
1 7 11
3 5 14

The first few rows are not sorted properly as per the output. Please help me out.

qsort kruskals-algorithm struct sorting c
1 Answers

The comparison function must return one of the following values, negative, zero or positive value, depending on whether the first compared elements is greater than, equal to or less than the second compared element for the descending sorting.

So this function definition

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return (x->cost > y->cost)?1:0;
}

is incorrect.

Instead you could write the following way (provided that you are going to sort the array in the descending order

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( x->cost < y->cost ) - ( y->cost < x->cost );
}

If you want to sort the array in the ascending order then the comparison function can look like

int compare(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( y->cost < x->cost ) - ( x->cost < y->cost );
}

Here is a demonstration program.

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

typedef struct node{
    int a;
    int b;
    int cost;
}node;

int ascending(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( y->cost < x->cost ) - ( x->cost < y->cost );
}

int descending(const void* a,const void* b){
    const node* x = *(node**)a;
    const node* y = *(node**)b;
    return ( x->cost < y->cost ) - ( y->cost < x->cost );
}

int main(void) 
{
    node * arr[] =
    {
        malloc( sizeof( node ) ), malloc( sizeof( node ) ), malloc( sizeof( node ) )
    };

    const size_t N = sizeof( arr ) / sizeof( *arr );

    arr[0]->a = 2;
    arr[0]->b = 5;
    arr[0]->cost = 4;    

    arr[1]->a = 7;
    arr[1]->b = 8;
    arr[1]->cost = 7;    

    arr[2]->a = 0;
    arr[2]->b = 1;
    arr[2]->cost = 4;

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    
    putchar( '\n' );
    
    qsort( arr, N, sizeof( *arr ), ascending );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    

    putchar( '\n' );

    qsort( arr, N, sizeof( *arr ), descending );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d %d %d\n", arr[i]->a, arr[i]->b, arr[i]->cost );
    }    

    putchar( '\n' );

    for ( size_t i = 0; i < N; i++ )
    {
        free( arr[i] );
    }    
}

The program output is

2 5 4
7 8 7
0 1 4

2 5 4
0 1 4
7 8 7

7 8 7
2 5 4
0 1 4
user_28772410
Related