0/5 (5 avis)
Snippet vu 6 694 fois - Téléchargée 22 fois
#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�s en un troisi�me tri� 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�s en un troisi�me tri� 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�rateur de gauche � droite int j=taille-1; // it�rateur de droite � 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); }
31 janv. 2008 à 13:18
31 janv. 2008 à 11:37
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+
30 janv. 2008 à 17:55
30 janv. 2008 à 10:50
A+
30 janv. 2008 à 09:32
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.