CS50x 2020 Problem Set 3 Tideman

Question

I have been working on the Tideman problem for a while now, and am still not able to find out how to implement the sort_pairs() function.

I have implemented my sort_pairs() function, but it is not working properly, in the sense that it compiles properly, but when I do check50, the red message comes up:

:( sort_pairs sorts pairs of candidates by margin of victory

Here is my pseudo code for the sort_pairs function:

for i = 0 to pair_count
{
    for j = 0 to pair_count - i - 1
    {
        if (preferences[pairs[i].winner][pairs[i].loser] > preferences[pairs[i + 1].loser][pairs[i + 1].winner])
        {
               swap(pairs[i], pairs[i+1]);
        }
     }
}

I have done everything I could, but to no avail. Any help would be kindly appreciated.

Answer 1

Clearly bubblesort algorithm has been used, but in the 5th line:

preferences[pairs[i].winner][pairs[i].loser] > preferences[pairs[i + 1].loser][pairs[i + 1].winner]

The basic functionality of bubblesort is wrong, i.e., indices of the inner loop should be considered while comparing. In addition, during comparison, pairs[i].winner should be kept first and pairs[i].loser should be kept second in preferences.

So the fifth line in the above pseudocode should be:

if (preferences[pairs[j].winner][pairs[j].loser] < preferences[pairs[j + 1].winner][pairs[j + 1].loser])
{
      ....
}

Answer 2

You did not show what you're swap function does, but this function will just be sorting so search for different sorting algorithms and implement it to your function, but if I'm understanding your code correctly your kind of implementing a bubble sort algorithm which may be the most inefficient one but that's ok efficiency doesn't really matter in this problem set. just search up bubble sort implementations in C it is a very simple algorithm and can solve your problem.