CS50 pset 3：Tideman sort_pairs 功能

Question

我需要一些帮助来理解这个函数背后的逻辑。这是我目前在 Tideman 中的 sort_pairs 功能：

// Sort pairs in decreasing order by the strength of victory
void sort_pairs(void)
{
    qsort(pairs, pair_count, sizeof(pair), compare);
    return;
}

// Function for sort_pairs
int compare(const void *a, const void *b)
{
    const pair *p1 = (const pair *) a;
    const pair *p2 = (const pair *) b;
    if (p1->winner < p2->winner)
    {
        return -1;
    }
    else if (p1->winner > p2->winner)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

这并没有清除 check50，我上网查找如何解决这个问题。似乎大多数函数都是比较首选项数组中的值（例如 preferences[pairs[i].winner][pairs[i].loser]）。我之前的函数 vote、record_preferences 和 add_pairs 都清除了 check50。我还没有超过 sort_pairs。

为什么我不能直接从 pairs 数组比较胜利的强度，因为我已经存储了数据？

Answer 1

你不需要把它弄得这么复杂，你可以在这里使用你自己的排序。我们来试试简单的插入排序-

void sort_pairs()
{
    pair temp;
    for (int i = 1, j; i < pair_count; i++)
    {
        temp = pairs[i];
        j = i - 1;
        for (; j >= 0 && preferences[pairs[j].winner][pairs[j].loser] < preferences[temp.winner][temp.loser]; j--)
        {
            pairs[j + 1] = pairs[j];
        }
        pairs[j + 1] = temp;
    }
}

pair 结构看起来像-

typedef struct
{
    int winner;
    int loser;
}
pair;

解释：-

我们遍历 pairs 数组中的每对元素 - 从 1 开始，因为我要与 上一个 元素 (j = i - 1)
现在我们检查当前元素之前的所有元素，并将它们与键进行比较 - preferences[pairs[INDEX].winner][pairs[INDEX].loser]

这是您应该作为排序依据的关键字。 preferences[WINNER_ID][LOSER_ID] 表示 比 LOSER_ID 更喜欢 WINNER_ID 的人数。

差不多就这些了！它只是一种插入排序，但 key 是重要的部分。

CS50 pset 3：Tideman sort_pairs 功能

CS50 pset 3: Tideman sort_pairs function

quicksort

cs50