Sorting an array of structures by a non-member of the struct

user_14784198 0
Viewed 58

Person is a struct that contains 5 char arrays and nothing else.

Score is a float type number that I obtained from a function that uses some of Person fields to calculate it.

I don't wanna add score as a field in the struct Person for complicated reasons.

The goal is to print Person's information (fields) based on how high the score is (from lowest to highest), in order to do that I made this struct to try to connect the score to its corresponding person.

typedef struct PersonWithAScore {
    Person* P;                    
    float score;
};

(also, is creating that struct even the right thing to do? )

 PersonWithAScore *PersonScores = (PersonWithAScore*)malloc(number_of_scores*sizeof(PersonWithAScore));
       
// a for loop is happening here, so I can get all my scores and person(s) in that table, so that I start sorting them
       PersonScores[i].Person = &query;        // query is a Person type
       PersonScores[i].Score = match;      // match is what the score function returns
.
.      
.
// that is just a incomplete implementation I tried, you can just skip through and just read after the code

void swap(float *xp, float *yp)  // used in bubblesort
{  
   float temp = *xp;  
   *xp = *yp;  
   *yp = temp;  
}
void BubbleSort(PersonWithAScore* PWS, int n)    //n = number of scores
{                                                // void type? I might need to return an array (sorted)
 PersonWithAScore* Temp = PWS;
 int i, j;  
   for (i = 0; i < n-1; i++)      
   for (j = 0; j < n-i-1; j++)                  // m not so sure it's working, I didn't get to test it
       if (PWS[j].score > PWS[j+1].score)       
           swap(&PWS[j].score, &PWS[j+1].score);
 return 0;
}

So after that, I'm hoping to get a sorted array of scores (what initially was PersonScores[]) . Optimally, I would want to go through the array while I'm printing out Person's information that are associated to each score, that is my first concern.

My second concern, is I'm not sure what sorting is proper in a big database (m currently working with a static database that contains a 100 of Person)

is it better to implement a quicksort algorithm in that case? I figured it takes a lot of memory, but it is significantly faster than the bubble sort, I'm trying to get a good balance of both speed and minimizing memory usage. Any ideas ?

sorting c arrays
1 Answers

You can use qsort() to sort the array of structures and recompute the scores on the fly in the comparison function:

float computePersonScore(Person *p) {
    /* compute the score from the person's data */
    ...
}

int compare_scores(const void *e1, const void *e2) {
    float f1 = computePersonScore(e1);
    float f2 = computePersonScore(e2);
    return (f1 > f2) - (f1 < f2);
}

...
    Person array[n];
    ...
    qsort(array, n, sizeof(*array), compare_scores);
...

If computePersonScore() needs a second argument, you can use qsort_r if your system supports it:

float computePersonScore(Person *p, Person *ref) {
    /* compute the score from the person's data */
    ...
}

int compare_scores(const void *e1, const void *e2, void *opaque) {
    float f1 = computePersonScore(e1, opaque);
    float f2 = computePersonScore(e2, opaque);
    return (f1 > f2) - (f1 < f2);
}

...
    Person array[n];
    Person *reference = ...;
    ...
    qsort_r(array, n, sizeof(*array), compare_scores, reference);
...
user_45932670
Related