I'm trying to evaluate whether the method I'm using to find if a candidate has won the race has too much overhead. I'm certain there are other ways to do this, but below is the first that came to mind:
Sort the candidates array (or really, a copy of the array) in descending order and then check if the first element in the sorted array is >= the number of votes needed to win, as shown below:
bool print_winner(void)
{
candidate fwd_candidates[MAX_CANDIDATES]; //dummy array to be fwd sorted.
candidate rev_candidates[MAX_CANDIDATES];//dummmy array to be rev sorted.
memcpy(fwd_candidates,candidates,sizeof(candidates));//copy candidates into fwd_candidates.
memcpy(rev_candidates,candidates,sizeof(candidates));//copy candidates into rev candidates
bubble_sort_candidates(rev_candidates, candidate_count, false);//reverse sort rev_candidates
bubble_sort_candidates(fwd_candidates, candidate_count, true);//fwd sort fwd_candidates
int winning_number = voter_count/2 + 1; //1 more vote than floored half of voters.
if(rev_candidates[0].votes >= winning_number)//if the highest vote is >= the winning number.
{
printf("%s\n",rev_candidates[0].name);
return true;
}
// TODO
return false;
}
This seems like overkill, am I wrong? The other method I thought of was simply looping through the original candidates array in a for (int i = 0; i < candidate_count; i++) loop and printing candidates[i].name if candidates[i].votes >= winning_number.
I suspect I can find other uses for my sorted dummy arrays in print_winner(), if that's the case, is there an argument for running two O(n^2) algorithms on arrays? I'm thinking that since the arrays are constrained to be small, this shouldn't be too bad. But if there were some election with dozens of candidates (as certainly never happens in the real world), then my first method could be a bit slow.
I haven't figured out how to implement merge sort yet, and don't want to just copy someone else's code.
