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.

Answer 1

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

Answer 2

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

Answer 3

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