Детали реализации тестирования для автоматизированной оценки алгоритмов сортировки

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

Заставьте их написать общую сортировку, которая сортирует (скажем) 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...)

ИЗМЕНИТЬ, ЧТОБЫ ДОБАВИТЬ: Альтернативой, которая может лучше обобщать вещи, отличные от конкретных алгоритмов сортировки, было бы заставить их написать общую сортировку, берущую начало и конец итераторов определенного типа и инструментирующую арифметику указателя и операторы разыменования для итераторов, которые вы им передаете.