Sorting an array of structs Efficiently

Question

I am sorting an array of structs using qsort, and I am looking for a more efficient way to extract the top three highest scores by partially sorting the array. My structure looks like this:

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

and I have malloced an array of structures like this:

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

The way I sort this array of structures is by first sorting the scores, and if the scores have ties, then sort by the player number.

My code looks like this with qsort:

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

#define SIZE 6
#define MAX 3

int scorecmp(const void *a, const void *b);
int ComparePlayerScore( const void* ap , const void* bp );
int CompareInt( const int a , const int 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), ComparePlayerScore);

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

    free(players);

    return 0;
}

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 CompareInt( a->player_num , b->player_num );
    }
    else if( a->score > b->score ) {
        return -1;
    }
    else {
        return 1;
    }
}

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

    return 0;
}

I am just looking for another way to do this, but a more efficient way to extract the top 3 the scores, along with the respective player numbers. Like a way where I can extract the top three elements of the array without having to sort the whole array first everytime.

Yeah, I have been experimenting with this, and trying to make it work with qsort but I can't seem to do this without sorting the whole array first. It seems like using an array of structures is making it more difficult. — RoadRunner
– RoadRunner, Commented Oct 16, 2016 at 17:08
I'd say don't worry about performance at this level. Your array has only size 6, so it is not worth optimizing away the three comparisons that might be redundant. Keep your code simple. And, if you later have measured that this part of the program is by far the slowest, only then should you optimize it. — Roland Illig
– Roland Illig, Commented Oct 16, 2016 at 17:09
Do you need to (partially) sort the array, or just find the index values of the 3 elements with the highest scores? — Weather Vane
– Weather Vane, Commented Oct 16, 2016 at 17:10
Yeah, it's just that, I am curious about the performance when the array gets really big. But I am not sure how to optimize it theoretically for that. — RoadRunner
– RoadRunner, Commented Oct 16, 2016 at 17:10

Weather Vane · Accepted Answer · 2016-10-16 17:45:38Z

This is my offering. Since you have #define MAX for how many top scores you want to find, I have considered that.

The program makes a single pass of the data, and 1 pass of the topmost for each of the records. I have used a fixed array, you'll have to adapt to your needs.

#include <stdio.h>

#define SIZE 6
#define MAX 3

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

int main(int argc, char *argv[])
{
    player_t players[SIZE] = {{2.0, 2}, {4.0, 5}, {1.0, 4}, {1.0, 1}, {5.0, 3}, {4.0, 6}};
    int order[MAX+1] = {0};
    int found = 1;
    int i, j;
    int bigger;

    for(i = 1; i < SIZE; i++) {
        bigger = 0;
        for(j = 0; j < found; j++) {
            if(players[i].score > players[ order[j] ].score) {
                bigger = 1;
                break;
            }
            else if(players[i].score == players[ order[j] ].score && 
                    players[i].player_num < players[ order[j] ].player_num) {
                bigger = 1;
                break;
            }
        }
        if(bigger) {
            memmove(order + j + 1, order + j, (found - j) * sizeof order[0]);
            order[j] = i;
            if(found < MAX) {
                found++;
            }
        }
    }

    for(i = 0; i < found; i++) {
        printf("%d %f\n", players[ order[i] ].player_num, players[ order[i] ].score); 
    }
    return 0;
}

Program output:

3 5.000000
5 4.000000
6 4.000000

Roland Illig · Accepted Answer · 2016-10-16 18:34:46Z

1

Just a simple try, see online demonstration on http://ideone.com/8A1lnP.

struct top3_players {
  player_t *top[3];
};

void top3_determine(struct top3_players *top, player_t *players, size_t n) {
  player_t *top1 = NULL;
  player_t *top2 = NULL;
  player_t *top3 = NULL;
  for (size_t i = 0; i < n; i++) {
    player_t *player = &players[i];
    if (top1 == NULL || ComparePlayerScore(player, top1) < 0) {
      top3 = top2;
      top2 = top1;
      top1 = player;
    } else if (top2 == NULL || ComparePlayerScore(player, top2) < 0) {
      top3 = top2;
      top2 = player;
    } else if (top3 == NULL || ComparePlayerScore(player, top3) < 0) {
      top3 = player;
    }
  }
  top->top[0] = top1;
  top->top[1] = top2;
  top->top[2] = top3;
}

edited Oct 16, 2016 at 18:34

answered Oct 16, 2016 at 17:31

Roland Illig

41.9k12 gold badges91 silver badges127 bronze badges

2 Comments

Jonathan Leffler Over a year ago

Is the dummy comparator educational in some way?

Roland Illig Over a year ago

No, it was just to make my code compilable on its own when I pasted it into ideone. I deleted it.

ad absurdum · Accepted Answer · 2016-10-16 19:58:51Z

Here is a solution that keeps track of the top three scores by storing pointers to them. When you add a player or change a score, an update function is called to keep the top-score list current. The advantage here is that you only ever need to iterate over a list of three elements. I modified your original code to demonstrate how this might work:

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

#define SIZE 6
#define MAX 3

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

void update_topscores(player_t **top, player_t *pplayer);

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));
    player_t **topscores = calloc(3, sizeof(player_t *));

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

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

    puts("Top Scores");
    for (i = 0; i < 3; i++) {
        printf("Player %d: Score: %.3f\n",
               topscores[i]->player_num, topscores[i]->score);    
    }

    /* Change score for player 4 */
    players[3].score = 0.755;
    update_topscores(topscores, &(players[3]));
    puts("New Top Scores");
    for (i = 0; i < 3; i++) {
        printf("Player %d: Score: %.3f\n",
               topscores[i]->player_num, topscores[i]->score);
    }

    free(players);
    free(topscores);

    return 0;
}

void update_topscores(player_t **top, player_t *pplayer)
{
    int i;
    player_t *temp;

    for (i = 0; i < 3; i++)
        if (top[i] == NULL) {
            top[i] = pplayer;
            return ;
        }
    for (i = 0; i < 3; i++) {
        if ((pplayer->score) > (top[i]->score)) {
            temp = top[i];
            top[i] = pplayer;
            update_topscores(top, temp);
            break;
        }
    }

    return ;
}

You can see that there is a function update_topscores() that is used to update the list. In the above code, this is used when building the initial list of players. Then, when the score of Player 4 is updated, the function is called again, resulting in a new list of top scores. The list is not sorted, but it would be easy to do so if desired, and you would only be sorting a list of three entries.

There was an additional allocation for three pointers to player pointers, topscores, which must of course be freed at the end.

Here is a sample output:

Player 1: Score: 0.765
Player 2: Score: 0.454
Player 3: Score: 0.454
Player 4: Score: 0.345
Player 5: Score: 0.643
Player 6: Score: 0.532
Top Scores
Player 1: Score: 0.765
Player 5: Score: 0.643
Player 6: Score: 0.532
New Top Scores
Player 1: Score: 0.765
Player 4: Score: 0.755
Player 5: Score: 0.643

Collectives™ on Stack Overflow

Sorting an array of structs Efficiently

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related