Sorting Tied Structure Elements

Question

I am trying to sort an array of structures using qsort. I have a structure which looks like this:

typedef struct {
    double score;
    int player_num;
} player_t;

And I have created an array of structures for six players like this:

player_t *players = malloc(6 * sizeof(player_t));

And the data I am inserting if from these two arrays:

int player_numbers[] = {1, 2, 3, 4, 5, 6};
double scores[] = {0.765, 0.454, 0.454, 0.345, 0.643, 0.532};

So far I am trying to sort this array of structures by scores, and if there are ties in the scores, then the player numbers must be sorted. I am so far get this output, from sorting the scores:

Player 1: Score: 0.765
Player 5: Score: 0.643
Player 6: Score: 0.532
Player 3: Score: 0.454
Player 2: Score: 0.454
Player 4: Score: 0.345

When I what I really want is this:

Player 1: Score: 0.765
Player 5: Score: 0.643
Player 6: Score: 0.532
Player 2: Score: 0.454
Player 3: Score: 0.454
Player 4: Score: 0.345

Whereby Player 2 and Player 3 swapped positions because they had the same scores, so their respective player numbers were sorted instead. The rest of the array remained the same.

I have so far sorted this array of structures just from the scores itself, which produced the first output. My code looks like this:

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

#define SIZE 6

int scorecmp(const void *a, const void *b);

typedef struct {
    double score;
    int player_num;
} player_t;

int
main(int argc, char *argv[]) {
    int i;

    int player_numbers[] = {1, 2, 3, 4, 5, 6};
    double scores[] = {0.765, 0.454, 0.454, 0.345, 0.643, 0.532};

    player_t *players = malloc(SIZE * sizeof(player_t));

    for (i = 0; i < SIZE; i++) {
        players[i].score = scores[i];
        players[i].player_num = player_numbers[i];
    }

    qsort(players, SIZE, sizeof(*players), scorecmp);

    for (i = 0; i < SIZE; i++) {
        printf("Player %d: Score: %.3f\n", players[i].player_num, players[i].score);
    }

    free(players);

    return 0;
}

int
scorecmp(const void *x, const void *y) {
    if ((*(double*)x > *(double*)y)) {
        return -1;
    }
    if ((*(double*)x < *(double*)y)) {
        return +1;
    }
    return 0;
}

Is there any way I can secondarily sort the tied scores, from using the player_num instead, and produce the second desired output?

Any help would be appreciated.

2501 · Accepted Answer · 2016-10-13T10:30:19.540

The way you're sorting is not correct. The comparison function receives a pointer to the struct not a pointer to the member of a struct.

The correct way to sort by the score is to use this comparison function in the qsort function:

int ComparePlayerScore( const void* ap , const void* bp )
{
    const player_t* const a = ap;
    const player_t* const b = bp;

    if( a->score < b->score )
    {
        return -1;
    }
    else if( a->score > b->score )
    {
        return 1;
    }

    return 0;
}

If you want to make sure the players with identical score are sorted alphabetically, you will need to make another check in the sorting function. First check if the players have the same score, and then sort by their player number.

Using a naive¹ way to compare floating point, the function would be:

if( a->score == b->score )
{
    return CompareInt( a->player_num , b->player_num )
}
else if( a->score < b->score )
{
    return -1;
}
else
{
    return 1;
}

Where CompareInt is another function:

int CompareInt( const int a , const int b )
{
    if( a < b )
    {
        return -1;
    }
    else if( a > b )
    {
        return 1;
    }

    return 0;
}

¹ Using a simple comparison operator to compare floating point can be problematic, see: How should I do floating point comparison?

Sorting Tied Structure Elements

1 Answers1