Class template des principaux tris de tableaux

0/5 (5 avis)

Snippet vu 6 694 fois - Téléchargée 22 fois

Contenu du snippet

Une fois instaciée, vous pouvez passez un tableau en parametre , il sera trié par la methode de tri que vous choisissez .

Source / Exemple :


#include <iostream>
using namespace std;
template <typename TYPE>
class Tri{
    private:
    void permuter(TYPE&,TYPE&); // permutation de deux variables
    void fusionner(TYPE *,TYPE *,TYPE *,int,int,int); // Fusionner deux tabelaux tri&#65533;s en un troisi&#65533;me tri&#65533;
    public:
    void affichage(TYPE *,int); // affichage
    void triParSelection(TYPE *,int); // tri par selection
    void triParBulles(TYPE *,int); // tri par bulles
    void triParInsertion(TYPE *,int); // tri par insertion
    void triParFusion(TYPE *,int,int); // tri par fusion
    void triRapide(TYPE *,int); // tri rapide
};

// afficher un tableau
template <typename TYPE>
void Tri<TYPE>::affichage(TYPE t[],int taille){
    for(int i=0;i<taille;i++){
    cout<<t[i]<<"<";
    }
}

// permutation
template <typename TYPE>
void Tri<TYPE>::permuter(TYPE &x,TYPE &y){
    TYPE temp=x;
    x=y;
    y=temp;
}

// Fusionner deux tabelaux tri&#65533;s en un troisi&#65533;me tri&#65533;
template <typename TYPE>
void Tri<TYPE>::fusionner(TYPE t1[],TYPE t2[],TYPE t3[],int l1,int l2,int l3){
    int i=0;
    int j=0;
    int k=0;
    while((i<l1)&&(j<l2)){
    if(t1[i]<t2[j]){
        t3[k]=t1[i];
        i++;
    }else{
        t3[k]=t2[j];
        j++;
    }
    k++;
    }
    if(l1>l2){
        for(int cpt=i;cpt<l1;cpt++){
            t3[k]=t1[cpt];
            k++;
        }
    }else{
        for(int cpt=j;cpt<l2;cpt++){
            t3[k]=t2[cpt];
            k++;
        }
    }

}

// Tri par selection
template <typename TYPE>
void Tri<TYPE>::triParSelection(TYPE t[],int taille){
    for(int i=0;i<taille-1;i++){
	    int min=i;
	    for(int j=i+1;j<taille;j++)
            if(t[j]<=t[min])
            min=j;
        permuter(t[min],t[i]);
	}
}

// Tri par bulles
template <typename TYPE>
void Tri<TYPE>::triParBulles(TYPE t[],int taille){
    bool b=true;
	while(b){
	b=false;
	for(int i=0;i<taille-1;i++){
		if(t[i]>t[i+1]){
			permuter(t[i],t[i+1]);
			b=true;
		}
	}
	}

}

// Tri par insertion
template <typename TYPE>
void Tri<TYPE>::triParInsertion(TYPE t[],int taille){
    for(int i=1;i<taille;i++){
        TYPE x=t[i];
        int j=i-1;
        while((t[j]>x)&&(j>=0)){
            t[j+1]=t[j];
            j=j-1;
            }
            t[j+1]=x;
    }
}

// Tri par fusion
template <typename TYPE>
void Tri<TYPE>::triParFusion(TYPE t[],int d,int f){
    if(d<f){
    int q=(d+f)/2;
    triParFusion(t,d,q);
    triParFusion(t,q+1,f);
    TYPE t1[q],t2[q+1];
    for(int i=d;i<=q;i++)
    t1[i]=t[i];
    for(int j=q;j<=f;j++)
    t2[j]=t[j];
    fusionner(t1,t2,t,q,q+1,f);
    }
}

// Tri rapide
template <typename TYPE>
void Tri<TYPE>::triRapide(TYPE t[],int taille){
    if(taille<2)return;
    int i=1; // it&#65533;rateur de gauche &#65533; droite
    int j=taille-1; // it&#65533;rateur de droite &#65533; gauche
    TYPE pivot;
    pivot=t[0];
    while(j>=i)
        if(t[i]<=pivot)i++;
        else if(pivot<=t[j])j--;
        else permuter(t[i++],t[j--]);
    t[0]=t[j];
    t[j]=pivot;
    triRapide(t,j);
    triRapide(t+i,taille-i);

}

A voir également

Ajouter un commentaire Commentaires
mehdi7604
Messages postés
118
Date d'inscription
jeudi 11 mai 2006
Statut
Membre
Dernière intervention
6 mars 2015

31 janv. 2008 à 13:18
oui , je l'avais conuslté avant .
xkamen
Messages postés
26
Date d'inscription
vendredi 8 avril 2005
Statut
Membre
Dernière intervention
31 janvier 2008

31 janv. 2008 à 11:37
Bonjour,

J'avais réalisé il y a déjà un certain temps une source plus complète de tri, contenant une trentaine d'algorithmes de tri. Cela peut compléter ta source.

http://www.cppfrance.com/codes/LIBRAIRIE-CONTENANT-TRENTAINE-ALGORITHMES-TRI_41100.aspx

A+
mehdi7604
Messages postés
118
Date d'inscription
jeudi 11 mai 2006
Statut
Membre
Dernière intervention
6 mars 2015

30 janv. 2008 à 17:55
Non les tris principaux sont ceux traités , il existe bcp d'autres , mais j'ai choisi LES PRINCIPAUX .
Pistol_Pete
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
7
30 janv. 2008 à 10:50
Le bogosort... ca doit etre l'algo de tri le plus inutile qui existe. Pas besoin de perdre son temps a coder cet algorithme.

A+
cs_tibur
Messages postés
101
Date d'inscription
samedi 9 février 2002
Statut
Membre
Dernière intervention
5 mai 2009

30 janv. 2008 à 09:32
Il manque le bogosort ;)
cf : http://en.wikipedia.org/wiki/Bogosort
Thibaut

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.