Class template des principaux tris de tableaux

Soyez le premier à donner votre avis sur cette source.

Snippet vu 5 910 fois - Téléchargée 20 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

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

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

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+
Messages postés
118
Date d'inscription
jeudi 11 mai 2006
Statut
Membre
Dernière intervention
6 mars 2015

Non les tris principaux sont ceux traités , il existe bcp d'autres , mais j'ai choisi LES PRINCIPAUX .
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
6
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+
Messages postés
101
Date d'inscription
samedi 9 février 2002
Statut
Membre
Dernière intervention
5 mai 2009

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.