0

This seems to be a common problem where the check50 program indicates a problem with the sort_pairs function. Here was my implementation of that function:

int w;
int l;
int w1;
int l1;

for (int i=0; i < pair_count; i++)
{
    for (int j=0; j < pair_count; j++)
    {
        w = pairs[i].winner;
        l = pairs[i].loser;
        w1 = pairs[j].winner;
        l1 = pairs[j].loser;

        if (preferences[w][l] < preferences[w1][l1])
        {
            pairs[j].winner = w;
            pairs[j].loser = l;
            pairs[i].winner = w1;
            pairs[i].loser = l1;
        }
    }

}

return;

I've gone over the logic multiple times and it seems sound but check50 disagrees. Any ideas?

Improve this question

1 Answer 1

Reset to default
1

I think you're trying to use bubble sort, since you're swapping pairs[i] and pairs[j] if pairs[j] is stronger than pairs[i]. However, bubble sort always swaps adjacent elements, and i and j aren't adjacent in your algorithm. Try thinking really carefully about what two pairs you should be looking at an any one time.

Improve this answer
3
  • I think I may be trying to mix and match with my sorting algos. Conceptually I'm comparing the first element in the array to every other element in the array and swapping the two if the first element is smaller than the other elements. Iterate through then do the same starting with the second element. Iterate through and do the same for the third element. And so on until I have compared every element to every other element in the array. Maybe it's time consuming but it should work no?
    – Arvind R
    Commented Jun 9, 2020 at 23:39
  • No, it wouldn't work. Think about what happens when i = pair_count - 1 and j = 0. If pairs[i] is weaker than pairs[j] you'll swap them, but then a weaker pair will end up being first in the pairs array. I'd advise that you use one of the sorting algorithms discussed in the lecture/shorts, since those will definitely work. If you want to create one yourself you'll have to be very careful about making sure that it works. If you do that, you should write down an array of numbers and go through your algorithm step by step to make sure it works.
    – Llenk
    Commented Jun 10, 2020 at 16:15
  • Thanks, your explanation makes sense. I see the error in my logic. Anyway, I implemented a bubble sort and this function now works.
    – Arvind R
    Commented Jun 11, 2020 at 1:29

You must log in to answer this question.

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