RoadRunner RoadRunner - 1 month ago 6
C Question

Sorting an array of structs Efficiently

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

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