Testing implementation details for automated assessment of sorting algorithms

Question

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.

You're so vague. "I want something better" - you didn't tell what you want — Alexey S. Larionov
– Alexey S. Larionov, Commented May 9, 2022 at 15:10
Welcome to stackoverflow.com. Please take some time to read the help pages, especially the sections named "What topics can I ask about here?" and "What types of questions should I avoid asking?". Also please take the tour and read about How to Ask good questions. Lastly please read this question checklist. — Some programmer dude
– Some programmer dude, Commented May 9, 2022 at 15:13
Something more precise. Automated confirmation that they've implemented specifically what is requested. — William Kavanagh
– William Kavanagh, Commented May 9, 2022 at 15:15
That sounds like a human-level awareness, hard to put it into automation. At the very least, if you follow the algorithm's description during implementation, there's almost no way you would screw up complexity (maybe just by a O(1) which doesn't matter) — Alexey S. Larionov
– Alexey S. Larionov, Commented May 9, 2022 at 15:18
@AlexeyLarionov: I think this is actually a pretty definite question giving a pretty definite criterion for what is or isn't an answer. (E.g. see my answer below). Not every question is going to be along the lines of "give me step-by-step instructions to make a button in Qt a different color," and that's not only acceptable but, I'd argue, desirable. — Daniel McLaury
– Daniel McLaury, Commented May 9, 2022 at 15:49

Daniel McLaury · Accepted Answer · 2022-05-09 15:38:22Z

2

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.

edited May 9, 2022 at 15:38

answered May 9, 2022 at 15:15

Daniel McLaury

4,4641 gold badge18 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Caleth Over a year ago

While I really like this, you will have to be careful about allowing for a number of reasonable design decisions, e.g. the choice of pivot for quicksort.

Daniel McLaury Over a year ago

@Caleth: Yeah, doing a direct comparison like the above won't work for things that are really more of a "family" of algorithms. Perhaps it's an acceptable exercise for the instructor of an algorithms class to write an algorithm which can determine whether a list of comparisons could possibly arise from a quicksort or not.

Collectives™ on Stack Overflow

Testing implementation details for automated assessment of sorting algorithms

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related