Librairie contenant une trentaine d'algorithmes de tri

Télécharger le projet
Commenter

Description

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.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (xkamen)