Je poste ici une librairie contenant un grand nombre d'algorithmes de tri, dont les plus connus et les plus utilisés (comme le tir à bulles, le tri par sélection, le tri par insertion, le tri rapide, ...) qui ont déjà été déposé sur ce site. Je viens juste compléter toutes les librairies précédentes en ajoutant un grand nombre d'algorithmes de tri qui sont parfois des variantes améliorées des tris usuels. De plus, la librairie a été réalisée à l'aide de template afin de ne pas limiter les tris à certaines données.
Pourquoi ces différents tris ? Nombreuses sont les personnes qui souhaitent trié une liste ou un vecteur, et selon leur utilisation, certains tris peuvent être plus judicieux qu'un autre. Il n'en existe pas un qui soit meilleur que les autres, mais suivant le nombre de valeurs à trier, la distribution de ces valeurs, le nombre de valeurs différentes utilisées, le fait que ces valeurs puissent être déjà presque triées ou non, il conviendra de choisir un algorithme de tri précis. C'est pourquoi j'ai implémenté toutes ces méthodes, pour que chacun puisse les essayer.
Un fichier PDF accompagne la source afin d'expliquer en détail les différentes méthodes de tri.
Source / Exemple :
#include <cstdio>
#include <ctime>
#include "tri.h"
#include "chrono.h"
#define NODISP
#define MAXVALUE_1 256
#define MAXVALUE_2 2
#define MAXSIZE_1 4096
#define MAXSIZE_2 10
#define MAXSIZE_3 25
typedef int data; // A modifier pour essayer d'autres types de valeur
std::vector<data> vector, vectorTrie;
int size;
int maxvalue;
Chrono chrono;
/*********************************************************************************************/
inline int compareFunc(const void* elem1, const void* elem2)
{
if (*(data*)elem1 > *(data*)elem2) return 1;
else if (*(data*)elem1 < *(data*)elem2) return -1;
else return 0;
}
inline unsigned int keyFunc (const void *elem)
{
return unsigned int(*(data*)elem);
}
/*********************************************************************************************/
void ComparisonSort(char method)
{
// Nom du tri en cour
printf("> %s : ",NameOfSort(method).c_str());
// Préparation au tri
vectorTrie = vector;
chrono.Start();
// Tri
Sort<data>(method,vectorTrie,size,compareFunc);
// Récupération et affichage du temps écoulé
float Time = chrono.GetDiff_ms();
printf("%f ms > ",Time);
// Vérification si le tri a été bien effectué
if (VerifySort<data>(vectorTrie,size,compareFunc)) printf("OK\n");
else printf("FAILED\n");
}
void KeySort(char method)
{
// Nom du tri en cour
printf("> %s : ",NameOfSort(method).c_str());
// Préparation au tri
vectorTrie = vector;
chrono.Start();
// Tri
Sort<data,unsigned int>(method,vectorTrie,size,maxvalue,keyFunc);
// Récupération et affichage du temps écoulé
float Time = chrono.GetDiff_ms();
printf("%f ms > ",Time);
// Vérification si le tri a été bien effectué
if (VerifySort<data>(vectorTrie,size,compareFunc)) printf("OK\n");
else printf("FAILED\n");
}
void VerificationTime()
{
// Démarrage du chrono
chrono.Start();
// Vérification des données triées
VerifySort<data>(vectorTrie,size,compareFunc);
// Récupération du temps écoulé
float Time = chrono.GetDiff_ms();
// Affichage du temps écoulé
printf("> Etape de verification : %f ms\n",Time);
}
/*********************************************************************************************/
void Test_with_RandomSort_and_SlowSort()
{
for (char method=NORMAL_SORT; method<=SHEAR_SORT; method++)
ComparisonSort(method);
for (; method<=FLASH_SORT; method++)
KeySort(method);
}
void Test_without_RandomSort_neither_SlowSort()
{
for (char method=NORMAL_SORT; method<=SHEAR_SORT; method++)
if (method<BOGO_SORT || (method>QUANTUM_BOGO_SORT && method!=STOOGE_SORT && method!=PERMUTATION_SORT))
ComparisonSort(method);
for (; method<=FLASH_SORT; method++)
KeySort(method);
}
void InitSort(int n, int s, int m)
{
// Message d'initialisation
size = s; maxvalue = m;
printf("Test %d : cas d'un vecteur de %d valeurs comprises entre 0 et %d\n",n,size,maxvalue-1);
// Choix de la taille du vecteur
vector.resize(size);
// Remplissage du vecteur
for (int i=0; i<size; i++) vector[i] = data(rand()%m);
}
/*********************************************************************************************/
main()
{
// Message de bienvenue
printf("Bienvenue dans le test des algorithmes de tri d'un vecteur\n\n");
// Initialisation du générateur pseudo aléatoire
srand ( (unsigned int)time(NULL) );
/**************************************************************************************************/
InitSort(1,MAXSIZE_2,MAXVALUE_1);
Test_with_RandomSort_and_SlowSort();
printf("\n");
/**************************************************************************************************/
InitSort(2,MAXSIZE_3,MAXVALUE_2);
Test_with_RandomSort_and_SlowSort();
printf("\n");
/**************************************************************************************************/
InitSort(3,MAXSIZE_1,MAXVALUE_1);
Test_without_RandomSort_neither_SlowSort();
printf("\n");
/**************************************************************************************************/
InitSort(4,MAXSIZE_1,MAXVALUE_2);
Test_without_RandomSort_neither_SlowSort();
printf("\n");
/**************************************************************************************************/
VerificationTime();
printf("\n");
}
Conclusion :
Dans la source, il me reste encore 2 tris à implémenter : le 'SpreadSort' et le 'LibrarySort'. Si quelqu'un a des suggestions à faire pour améliorer les méthodes implémentées dans cette source, ou même des idées pour en rajouter d'autres, n'hésitez pas, je complèterais la source.
Le tri d'une liste chainée ou d'une map n'a pas été implémenté. Seul les tableaux et les vecteurs sont utilisés.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.