Testing implementation details for automated assessment of sorting algorithms-CodePudding

I'm looking at automated assignments for an introductory algorithms and data structures course. Students submit code, I run boost tests on them, the number of passed tests gives a grade, easy. But I want to assess sorting algorithms, for example "Implement bubble-, insertion-, selection- and merge-sort". Is there a clever way to test the implementations of each to know they did in fact implement the algorithm requested?

Obviously I can check they sorted the inputs. But what I really want is something better than just comparing the timings for various inputs to check complexities.

CodePudding user response：

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

Make them write a generic sort that sorts (say) a std::vector<T>, and then in your unit test provide a class where you overload the comparison operator used by the sorting algorithm to log which objects it's sorting. At the end your test can examine that log and determine if the right things were compared to one another in the right order.

What distinguishes one sorting algorithm from another is ultimately the order in which elements are compared.

EDIT: Here's a sample implementation. Not the cleanest or prettiest thing in the world, but sufficient as a throwaway class used in a unit test.

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;

Sample usage in a unit test:

    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);

This checks that studentSort implements the same sorting algorithm as std::sort. (Of course, what it doesn't check is that studentSort doesn't just forward to std::sort...)

EDIT TO ADD: An alternative, which may generalize better to things other than sorting algorithms specifically, would be to make them write a generic sort taking begin and end iterators of a particular type and instrumenting the pointer arithmetic and dereferencing operators for the iterators you hand them.