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.
        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.


It does depend on which type of election it is (there were 3 different versions.) Generally speaking though, if you're just looking for the person with the highest number of votes, all you need to do is scan the list once and keep track of the highest number of votes and the name of the candidate. A single pass through the list, n, is better than a sort, n * n.

| improve this answer | |
  • Makes sense, thanks! I was able to complete runoff with my less than optimal method, so I'll go back and optimize at some point. – Nate May 13 at 16:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .