-1

I have to write a program that uses the qsort function to sort a vector of points in the Cartesian plane. Each point is formed by a pair of coordinates (x, y). Points must be sorted by ascending x-axis. With the same x-axis, y-axis is ordered by descending.

This is a sample input:

5 (Struct numbers)
2 5
12 2
2 7
3 4
2 2

With the output:

2 7
2 5
2 2
3 4
12 2

Now, this is my code:

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

typedef struct x_y
{
    int x;
    int y;
}coordinates;
typedef coordinates *coordinatesList;

int compare(const void *a, const void *b)
{
    coordinates *a1 = (coordinates *)a;
    coordinates *b1 = (coordinates *)b;
    if (a1->x > b1->x)
        return 1;
    else if (a1->x < b1->x)
        return (-1);
    else if (a1->x == b1->x)
    {
        if (a1->y < b1->y)
            return 1;
        else if (a1->y > b1->y)
            return (-1);
        else
            return 0;
    }
}

int main()
{
    int n, i;
    scanf("%d", &n);
    coordinatesList *A = (coordinatesList*)malloc(n * sizeof(coordinates));
    for (i = 0; i < n; i++)
    {
        A[i] = (coordinatesList)malloc(sizeof(coordinates));
        scanf("%d%d", &A[i]->x, &A[i]->y);
    }
    qsort(A, n, sizeof(coordinates*), compare);
    for (i = 0; i < n; i++)
        printf("%d %d\n", A[i]->x, A[i]->y);
    return 0;
}

whith his wrong output:

2 7
3 4
2 2
2 5
12 2

If I try to separate the structs by element:

int compare(const void *a, const void *b)
{
    coordinates *a1 = (coordinates *)a;
    coordinates *b1 = (coordinates *)b;
    int a_x = a1->x;
    int a_y = a1->y;
    int b_x = b1->x;
    int b_y = b1->y;
    if (a_x > b_x)
        return 1;
    else if (a_x < b_x)
        return (-1);
    else if (a_x == b_x)
    {
        if (a_y < b_y)
            return 1;
        else if (a_y > b_y)
            return (-1);
        else
            return 0;
    }
}

...gives me a different wrong output:

2 2
12 2
2 7
3 4
2 5

2 Answers 2

3

The compare function gets pointers to the elements to be sorted, so here it gets pointers to coordinates pointers. The correct beginning is:

int compare(const void *a, const void *b)
{
    const coordinates *a1 = *(const coordinates **)a;
    const coordinates *b1 = *(const coordinates **)b;

I added const because you shouldn't cast away const-ness, even if it doesn't matter here. You would notice if you used warnings with the compilation.

You should also use sizeof(coordinates) in the call to qsort, not sizeof(coordinates*), because otherwise the sort function can't know how big your elements are, but these two probably have the same value here.

1
  • Thank you very much for the answer, that really solved my problem out!
    – Maggiorana
    Commented Apr 9, 2018 at 15:16
2

For starters according to the C Standard the function main without parameters shall be declared like

int main( void )

In this declaration

coordinatesList *A = (coordinatesList*)malloc(n * sizeof(coordinates));

you have to use expression sizeof( coordinatesList ) instead of the expressions sizeof( coordinates ).

In the function compare you have to write

int compare(const void *a, const void *b)
{
    const coordinatesList a1 = *( const coordinatesList *)a;
    const coordinatesList b1 = *( const coordinatesList *)b;
    //...

Here is a demonstrative program

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

typedef struct x_y
{
    int x;
    int y;
} coordinates;

typedef coordinates *coordinatesList;

int compare( const void *a, const void *b )
{
    const coordinatesList a1 = *( const coordinatesList * )a;
    const coordinatesList b1 = *( const coordinatesList * )b;

    if ( a1->x < b1->x )
    {
        return -1;
    }
    else if ( b1->x < a1->x )
    {
        return 1;
    }
    else
    {
        if ( a1->y < b1-> y )
        {
            return 1;
        }
        else if ( b1->y < a1->y )
        {
            return -1; 
        }
        else
        {
            return 0;
        }
    }
}

int main(void) 
{
    const size_t N = 5;

    coordinatesList *A = malloc( N * sizeof( coordinatesList ) );

    for ( size_t i = 0; i < N; i++ )
    {
        A[i] = malloc( sizeof( coordinates ) );
    }

    A[0]->x = 2;  A[0]->y = 5;
    A[1]->x = 12; A[1]->y = 2;
    A[2]->x = 2;  A[2]->y = 7;
    A[3]->x = 3;  A[3]->y = 4;
    A[4]->x = 2;  A[4]->y = 2;

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d\t%d\n", A[i]->x, A[i]->y );
    }
    putchar( '\n' );

    qsort( A, N, sizeof( coordinatesList ), compare );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d\t%d\n", A[i]->x, A[i]->y );
    }
    putchar( '\n' );

    return 0;
}

Its output is

2   5
12  2
2   7
3   4
2   2

2   7
2   5
2   2
3   4
12  2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.