J'ai beaucoup d'algorithmes de tri différents qui ont tous la signature suivante:
void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);
4 Réponses :
L'étude définitive du tri est Bob Sedgewick la thèse de doctorat. Mais il y a beaucoup de bonnes informations dans ses manuels d'algorithmes et ce sont les deux premiers endroits que je rechercherais une suite de test et une méthodologie. Si vous avez eu un cours récent, vous en saurez plus que ce que je fais; La dernière fois que j'ai eu un cours, la meilleure méthode consistait à utiliser QuicksTort jusqu'à la partition de la taille 12, puis exécuter l'insertion Trier sur l'ensemble de la matrice. Mais les réponses changent aussi vite que le matériel.
La programmation de Jon Bentley Les livres de Perls ont d'autres informations sur le tri.
Vous pouvez rapidement préparer une suite de test contenant
entiers aléatoires
entiers triés
entiers triés inversés
entiers triés, légèrement perturbés
Si la mémoire sert, ce sont les cas les plus importants pour un algorithme de tri.
Si vous souhaitez trier des tableaux qui ne correspondent pas au cache, vous devez mesurer les effets de cache. Valgrind est efficace si lent.
Ce site affiche les différents algorithmes de tri utilisant quatre groupes: http://www.sorting-algorithms.com/
Outre les quatre groupes de la réponse de Norman, vous souhaitez vérifier les algorithmes de tri avec collection de nombres qui ont quelques similitudes dans les numéros:
Modification du nombre d'éléments de la collection est également une bonne pratique Vérifiez chaque algorithme avec 1k, 1m, 1g, etc. pour voir quelles sont les implications de mémoire de cet algorithme.
Cette discussion détaillée , ainsi que relier à un grand nombre de web Pages Vous êtes susceptible de trouver utile, décrit également un ensemble utile de données d'entrée pour tester les algorithmes de tri (voir la page liée pour des raisons). Résumation:
sortperf.py possède une suite bien sélectionnée de cas de test de référence et a été utilisée pour prendre en charge l'essai trouvé ICI Notez que, au plus tard enfin, Java peut également se déplacer vers Timsort, grâce à Josh Block (voir ici ), donc j'imagine qu'ils ont écrit leur propre version des cas de test de référence - Cependant, je ne peux pas facilement Trouvez une référence à elle. (Timsort, une variante de Mergesort naturelle itérative stable, adaptative et itérative, est particulièrement adaptée aux langues avec une sémantique de référence à des objets tels que Python et Java, où le «mouvement de données» est relativement bon marché [[puisque tout ce qui est déjà déplacé est des références, des références AKA Pointeurs , pas des blobs de taille sans bornes ;-)]], mais les comparaisons peuvent être relativement coûteuses [[[car il n'y a pas de limite supérieure à la complexité d'une fonction de comparaison - mais cette suppression de toute langue où le tri peut être personnalisé via une coutume Fonction de comparaison ou d'extraction de clé]]]).
Il ne sert à rien de transmettre un argument de type valorisation comme const. Je suppose que cela ne fait aucun mal, mais c'est ... inutile et verbeux.
Si les algorithmes de tri sont les algorithmes standard correctement implémentés, des données d'analyse de complexité sont déjà disponibles (Google IT), quel est le but de faire une analyse Saiting?
@unwind: Je préfère que les valeurs constantes soient déclarées comme des valeurs constantes. @learner: a) Beaucoup ne sont pas standard. b) J'ai des algorithmes qui effectuent différemment par machine en raison de la mémoire et de la mise en cache, malheureusement les généralisations ne sont pas acceptables dans ces cas.
Cela ressemble à un projet que j'ai dû faire pour une classe de données de classe il y a des années :) Après cela, il était inséré, supprime et itérer sur diverses structures de conteneurs et comparer.