make testesimples permite algoritmos que não tratem repetição

[iagorrr]

Como o make testesimples utiliza apenas o arquivo input/10-reverso é possível que algoritmos que não tratem repetição resultem na mesma md5, dando a ilusão de corretude do algoritmo.

Exemplo

Utilizando um set do c++ para inserir os elementos (que ignora repetições) e depois iterando sobre os elementos gera o mesmo md5.

cppsetsort

#include <stdio.h>
#include <set>
#include "ordenacaomacros.h"

using namespace std;

struct Compare
{
  bool operator()(const Item &a,const Item &b) const
  {
    return less(a,b);
  }
};

int main(void)
{
  int t;
  int r;
  r=scanf("%d",&t);
  set<Item, Compare> st;
  for(int i=0;i<t;++i){
    Item it;
    r=scanf("%d",&it);
    st.insert(it);
  }

  for(auto &x : st)
    r=printf("%d\n",x);
  return 0;
}

Output do make testesimples

dummy 78968b953a8809e7af12ff461fa92e8a  -
bubblesort d9921bfb7d3f63b496265bdc0564b5b8  -
bubblesortsentinela d9921bfb7d3f63b496265bdc0564b5b8  -
combsort d9921bfb7d3f63b496265bdc0564b5b8  -
selectionsort d9921bfb7d3f63b496265bdc0564b5b8  -
selectionsortR d9921bfb7d3f63b496265bdc0564b5b8  -
insertionsortslow d9921bfb7d3f63b496265bdc0564b5b8  -
insertionsort d9921bfb7d3f63b496265bdc0564b5b8  -
shellsort d9921bfb7d3f63b496265bdc0564b5b8  -
quicksort d9921bfb7d3f63b496265bdc0564b5b8  -
quicksortinsertion d9921bfb7d3f63b496265bdc0564b5b8  -
quicksortM3 d9921bfb7d3f63b496265bdc0564b5b8  -
quicksortM3insertion d9921bfb7d3f63b496265bdc0564b5b8  -
mergesort d9921bfb7d3f63b496265bdc0564b5b8  -
insertionsortmetades d9921bfb7d3f63b496265bdc0564b5b8  -
systemqsort d9921bfb7d3f63b496265bdc0564b5b8  -
introsortquickmerge d9921bfb7d3f63b496265bdc0564b5b8  -
introsortquickmergelongjmp d9921bfb7d3f63b496265bdc0564b5b8  -
introsortquickheaplongjmp d9921bfb7d3f63b496265bdc0564b5b8  -
radixsort d9921bfb7d3f63b496265bdc0564b5b8  -
redblacktreesort d9921bfb7d3f63b496265bdc0564b5b8  -
cppsort d9921bfb7d3f63b496265bdc0564b5b8  -
cppsetsort d9921bfb7d3f63b496265bdc0564b5b8  -
pqsortsimple d9921bfb7d3f63b496265bdc0564b5b8  -
heapsort d9921bfb7d3f63b496265bdc0564b5b8  -
countingsort d9921bfb7d3f63b496265bdc0564b5b8  -

Fazendo as seguites alterações no make testesimples observa-se que que o md5 se altera, visto que o set eliminará os elementos repetidos produzindo um resultado diferente.

make testesimples

testesimples: $(BINARY)
    @for B in $(BINARY); do \
        REVERSO=$$(./$$B < input/10-reverso          | md5sum | cut -d ' ' -f 1); \
        REPETIDO=$$(./$$B < input/10-muitosrepetidos | md5sum | cut -d ' ' -f 1); \
        printf "$$B - [$$REVERSO]  [$$REPETIDO]\n"; \
    done

output :

dummy - [78968b953a8809e7af12ff461fa92e8a]  [f26514f89d6a83f820d2d0b5f37a13fb]
bubblesort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
bubblesortsentinela - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
combsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
selectionsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
selectionsortR - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
insertionsortslow - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
insertionsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
shellsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
quicksort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
quicksortinsertion - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
quicksortM3 - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
quicksortM3insertion - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
mergesort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
insertionsortmetades - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
systemqsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
introsortquickmerge - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
introsortquickmergelongjmp - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
introsortquickheaplongjmp - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
radixsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
redblacktreesort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
cppsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
cppsetsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [5e8c1c01f31c73ba3f2d4d119a0cccab]
pqsortsimple - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
heapsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]
countingsort - [d9921bfb7d3f63b496265bdc0564b5b8]  [d9f1169747cb90c598263d8aa517332e]