Eu tenho um monte de diferentes algoritmos de ordenação que todos têm a seguinte assinatura:
void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);
Há algum suites de teste para triagem que eu poderia usar para a finalidade de fazer comparações empíricas?
Esta discussão detalhada , bem como a ligação a um grande número de páginas web relacionadas que são susceptíveis de encontrar útil, também descreve um conjunto útil de dados de entrada para testar algoritmos de classificação (ver a página vinculada por razões). resumindo:
O estudo definitivo de classificação é Bob Sedgewick tese de doutorado 's. Mas há um monte de boas informações em seus livros de algoritmos, e esses são os dois primeiros lugares que eu iria procurar conjunto de testes e metodologia. Se você já teve um curso recente você vai saber mais do que eu; última vez que tive um curso, o melhor método era usar quicksort para baixo para partições de tamanho 12, em seguida, executar tipo de inserção em toda a matriz. Mas as respostas mudar tão rapidamente quanto o hardware.
Programação Perls livros de Jon Bentley tem algumas outras informações sobre a classificação.
Você pode rapidamente chicotear acima de um conjunto de testes contendo
inteiros aleatórios
inteiros ordenados
Reverter inteiros ordenados
inteiros ordenados, levemente perturbada
Se serve de memória, estes são os casos mais importantes para um algoritmo de ordenação.
Se você estiver olhando para classificar matrizes que não cabem no cache, você vai precisar para medir os efeitos de cache. valgrindé eficaz se lento.
sortperf.py tem um conjunto bem selecionados de casos de teste de benchmark e foi usado para apoiar o ensaio encontrados aqui e fazer timsort o tipo em Python lo que há muitos anos. Note-se que, finalmente, Java pode estar se movendo para timsort também, graças a Josh Block (ver aqui), Então eu imagino que eles têm escrito a sua própria versão dos casos de teste de benchmark - no entanto, não pode facilmente encontrar uma referência a ele. (Timsort, um estábulo, adaptáveis, iterativa variante mergesort natural, é especialmente adequado para idiomas com a semântica de referência-a-objeto, como Python e Java, onde "o movimento de dados" é relativamente barato [[uma vez que todos que já sendo movido é referências aka ponteiros , não bolhas de tamanho ilimitado ;-)]], mas as comparações podem ser relativamente caro `pois não há limite superior para a complexidade de uma função de comparação - mas isso vale para qualquer idioma em que a classificação pode ser personalizado através de uma comparação personalizada ou function` chave-extracção).
Este site mostra os vários algoritmos de ordenação utilizando quatro grupos: http://www.sorting-algorithms.com/
Além do grupo de quatro na resposta de Norman que pretende verificar os algoritmos de ordenação com coleção de números que têm algumas semelhanças nos números:
Alterar o número de elementos na coleção também é uma boa prática verificar cada algoritmo com 1K, 1M, 1G etc, para ver quais são as implicações de memória desse algoritmo.
