qsort
を使用して構造体の配列をソートしていますが、配列を部分的にソートすることで上位3つの最高点を抽出する効率的な方法を探しています。私の構造は次のようになります。構造体の配列を効率的にソート
typedef struct {
double score;
int player_num;
} player_t;
と私はこのような構造体の配列をmallocされている:
player_t *players = malloc(SIZE * sizeof(player_t));
私は構造体のこの配列をソート方法は、最初にスコアをソートすることであり、そして得点場合次に、選手の番号でソートします。
私のコードはqsort
で次のようになります。私はこれを行うには別の方法を探していますが、より効率的な方法は、それぞれのプレイヤー番号とともに、トップ3のスコアを抽出するために
#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;
}
。毎回配列全体をソートすることなく、配列の上位3要素を抽出できる方法と同じです。
私は[最近答え質問](http://stackoverflow.com/questions/40061974/partially-sorting-an-arrayこのフォローアップを推測します-c)。 –
ええ、私はこれを実験していて、 'qsort'でも動作させようとしていますが、まず配列全体をソートせずにはできません。構造体の配列を使用することは難しくなっているようです。 – RoadRunner
私はこのレベルでのパフォーマンスについて心配しないと言いたいと思います。あなたの配列のサイズは6だから、冗長かもしれない3つの比較を最適化する価値はありません。コードをシンプルに保つ。そして、プログラムのこの部分がはるかに遅いということを後で判断した場合は、それを最適化する必要があります。 –