自动评估排序算法的测试实现细节

Question

我正在为一门介绍性算法和数据结构课程研究自动作业。学生提交代码，我对他们进行升压测试，通过考试的次数给分数，很容易。但我想评估排序算法，例如“实现气泡-插入-选择-和合并排序”。是否有一种聪明的方法来测试每个实现，从而知道它们实际上实现了所请求的算法？

很明显，我可以检查他们对输入进行排序。但我真正想要的是比比较不同输入的时间来检查复杂性更好。

Answer 1

是否有一种聪明的方法来测试每个实现，从而知道它们实际上实现了所请求的算法？

让他们编写一个通用的排序(比如) std::vector<T>，然后在单元测试中提供一个类，在这个类中，您可以重载排序算法使用的比较操作符来记录它正在排序的对象。最后，您的测试可以检查日志，并确定是否以正确的顺序将正确的内容进行了比较。

区别于一种排序算法和另一种排序算法的最终是元素比较的顺序。

编辑：下面是一个示例实现。它不是世界上最干净或最漂亮的东西，而是一个单元测试中使用的一次性类。

struct S
{
  static std::vector<std::pair<int, int>> * comparisonLog;

  int x;

  S(int t_x) : x(t_x) { }

  bool operator <(const S & t_other) const
  {
      comparisonLog->push_back({x, t_other.x});
      
      return x < t_other.x;
  }
};

std::vector<std::pair<int, int>> * S::comparisonLog;

单元测试中的示例使用情况：

    std::vector<std::pair<int, int>> referenceComparisons, studentComparisons;

    const std::vector<S> values = { 1, 5, 4, 3, 2 };

    S::comparisonLog = &referenceComparisons;
    {
      auto toSort = values;
      std::sort(toSort.begin(), toSort.end());
    }

    S::comparisonLog = &studentComparisons;
    {
        auto toSort = values;
        studentSort(toSort);
        assert(std::is_sorted(toSort.begin(), toSort.end()));
    }

    assert(referenceComparisons == studentComparisons);

这将检查studentSort是否实现了与std::sort相同的排序算法。(当然，它没有检查的是studentSort不只是转发到std::sort.)

编辑以添加：--可能会更好地推广到排序算法以外的其他事物--将使它们编写一个泛型排序，获取特定类型的开始迭代器和结束迭代器，并对指针算法进行检测，并为您提交的迭代器取消引用运算符。