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

Question

我正在查看介绍性算法和数据结构课程的自动作业。同学提交代码，我运行 boost 测试，通过测试的数量给一个等级，easy。但我想评估排序算法，例如“实现冒泡排序、插入排序、选择排序和合并排序”。有没有一种聪明的方法来测试每个实现以了解它们确实实现了所请求的算法？

显然我可以检查他们对输入进行排序。但我真正想要的是比仅仅比较各种输入的时间来检查复杂性更好的东西。

Answer 1

Is there a clever way to test the implementations of each to know they did in fact implement the algorithm requested?

让他们写一个通用排序来排序（比如说）std::vector<T>，然后在你的单元测试中提供一个 class，你可以在其中重载排序算法使用的比较运算符来记录哪个它正在排序的对象。最后，您的测试可以检查该日志并确定正确的事物是否以正确的顺序相互比较。

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

编辑：这是一个示例实现。不是世界上最干净或最漂亮的东西，但足以作为单元测试中使用的一次性用品 class。

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

编辑添加： 另一种方法可能会更好地推广到特定排序算法之外的事物，它是让它们编写一个通用排序，采用 a 的开始和结束迭代器特定类型并为您交给它们的迭代器检测指针算术和取消引用运算符。

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

Testing implementation details for automated assessment of sorting algorithms

c++

automated-tests