Class template des principaux tris de tableaux

Commenter

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

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 (mehdi7604)