Tri par tas générique. rapide et efficace.

Télécharger le projet
Commenter

Description

Ben tout est dans le titre.
C'est un fichier .h
Puis tout est expliqué au début en commentaire.

Sauf la façon de fonctionner, mais la, faut me demander si vous avez vraiment envie.
Désolé, j'ai déjà expliqué ce soir. :)

Source / Exemple : 


/*


     
  •  Implémentation du tris par tas générique. Bloomwhite 2002-2004

 *


     
  • 	Simple fonction (en fait c'est un objet utilisé en fonction).

    •  
  • 	exemple: TriTas<int>(tab, taille(tab));	// ici, tab est un tableau d'entiers (int).

 *


     
  • 	Entrées:

    •  
  • 	Le premier argument est un tableau de type C (vecteur). Il peut être de type quelconque.

    •  
  • 	Le second argument est la taille du tableau en nombre d'éléments.

    •  
  • 		(ou du dernier élément +1 à trier)

    •  
  • 	Le troisième argument est optionnel:

    •  
  • 		c'est une fonction de comparaison selon laquelle va être trié le tableau,

    •  
  • 		si cette fonction est de type >, le tableau sera trié dans l'ordre croissant.

    •  
  • 		Si elle n'est pas précisée, l'opérateur > sera utilisé par défaut;

    •  
  • 		il faudra alors que cet opérateur soit définit pour le type contenu dans le tableau.

 *


     
  • 	Sorties:

    •  
  • 	Aucune sortie. Le tableau sera trié.

 *


     
  • 		A Public OpenSource Project.

    •  
  • /


#ifndef _TriTas_H_
#define _TriTas_H_

// Je fourni la fonction utilisée par défaut pour le tri.
// Pour des raisons aussi bien obscures que mystérieuses, j'ai pas pu la mettre dans la classe.
template<class Type>
inline bool _compare_defaut_tritas	(Type a, Type b) { return (a>b); }
// En fait, je pense que c'est parce qu'elle est utilisée en argument par défaut dans la classe.

template<class Type>
class TriTas
{
public:
	TriTas(Type*, int, bool (__cdecl*)(Type, Type)=_compare_defaut_tritas);	// Tableau,taille,fct
	~TriTas() {};
private:
	inline void echange(Type& a, Type& b)	{	Type temp= a; a= b; b= temp;	}
	bool (*compare)	(Type, Type);	// Donnée membre et non fonction (pointeur sur fonction).

	void entasser	(int =0);	// Par défaut entasser la racine.
	void construit	();			// Tri.

	int _taille;				// Taille du tableau.
	Type* _a;					// Tableau à trier.
};

template<class Type>
TriTas<Type>::TriTas(Type* a, int taille, bool (*comp)(Type, Type)) : _taille(taille), _a(a)
{
	compare = comp;
	construit();							// D'abord préparation
	for (--_taille; _taille > 0; --_taille)
	{
		echange(_a[_taille],_a[0]);			// Puis tri.
		entasser();
	}
}

template<class Type>
void TriTas<Type>::entasser(int noeud)
{
	int	max,
		gauche= 2*noeud+1,
		droite= gauche+1;
	max = noeud;
	if (gauche<_taille && compare(_a[gauche],_a[noeud]))	max = gauche;
	if (droite<_taille && compare(_a[droite],_a[max])  )	max = droite;

	if (max != noeud)
	{
		echange(_a[max],_a[noeud]);
		entasser(max);
	}
}

template<class Type>
void TriTas<Type>::construit()
{
	int last;
	for(last= _taille/2 - 1; last>=0; --last)	// on commence au dernier ayant
		entasser(last);							// un fils jusqu'au premier (la racine)
}

#endif //_TriTas_H_

Conclusion :


Ben voila. Souvent on cherche des algos de tri, ben la y'en a un. C'est l'un des plus puissant et moins contraignant existant.
Sinon utilisé la STL, il est dedans, c'est le même.
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 (TeLeTUbIz)