Tris de tableaux par les methodes les plus usuelles...

Commenter

Contenu du snippet

Comme l'indique le titre,c'est l'implémentation des tris dans les tableaux avec les méthodes les plus connues ( Bulle,Insertion,Quicksort,shell...)
Pour tous ceux qui auront à lire ce programme,merci de bien vouloir ajouter des commentaires (et si possible la note)pour que je puisse l'améliorer. Je suis debutant en c++,donc allez - mollo...
Vive CodesSources!!! Merci à ts pour ce site...

Source / Exemple : 


#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
using namespace std;
#define FAUX -1;
class tablo 
{
public:
void afficher(vector<int>&tab,int n) 
{
 for(int i=0;i<n;i++) cout<<tab[i]<<"  ";cout<<endl;
}
void permute(int &a,int &b) 
{ 
   int tmp;
   tmp=a;
   a=b;
   b=tmp;
}   
/********  tri bulle  **********/
void tri_bulle(vector<int>&tab,int n) {
    bool drapeau;
    do 
	{
      drapeau = false;
      for(int i=0 ; i<n-1 ; i++) {
	     if(tab[i] > tab[i+1])
		 { 
	       permute(tab[i],tab[i+1]);
	       drapeau = true;
		 }   
	  } 
	}while(drapeau == true);
    afficher(tab,n);
  }
void tri_insertion(vector<int>&tab,int n)
{
    for(int i=0;i<n;i++){
	insertion(tab,i);}
               afficher(tab,n);
}
void insertion(vector<int>&tab,int ind)
{
    int i,g,aux;
    i=ind-1;
    aux=tab[ind];
    g=0;
    while(i>=g+1 && tab[i]>aux)
	{
      tab[i+1]=tab[i];
      i--;
    }
      if(tab[g]>aux)
	  { 
        i=g-1;
        tab[g+1]=tab[g];
	  } 
    tab[i+1]=aux;
   
} 
/***********  tri shell ****************/
void tri_shell(vector<int>&tab,int n)
{
  int pas,i,j,tmp;
  for(pas = n/2 ;pas > 0;pas /= 2)
   for(i=pas;i<n;i++)
     for(j=i-pas;(j>=0)&&(tab[j]>tab[j+pas]);j -=pas)
     {
   tmp=tab[j];   //ou appeler simplement la fction permuter
   tab[j]=tab[j+pas];
   tab[j+pas]=tmp;
	 }
   afficher(tab,n);
}  
/**** recherche dichotomique  *****/
int dicho(vector<int>&tab,int &x)
{
    int a=0; int b=tab.size()-1; int m;
      while(a<b)
      {
	m=(a+b)/2;
	if(tab[m]<x) 
	{ 
	   a=m+1;
	} 
                else  
	 { 
	     if (tab[m]>x)
	     { 
	        b=m-1;
	     }  
	     else 
	    {
	        if(tab[m]==x)
	       {  
	           return m;
	       }  
	   }      
         }       
     }
cout<<"Nombre inexistant tableau"<<endl;
return FAUX;
} 
/************ tri Quicksort  ********/
int partition(int m,int n,vector<int>&tab) 
{
    int pivot = tab[m];  
    int i = m-1;
    int j = n+1;    // indice final du pivot 
  
    while (true) 
	{
      do 
	  {
        j--;
      } while (tab[j] > pivot);
      do 
	  {
        i++;
      }while (tab[i] < pivot);
      if (i<j) 
	  {
        int temp=tab[i];
        tab[i]=tab[j];
        tab[j]=temp;  
      } 
	  else 
	  {
        return j;
	  }
	} 
} 
void tri_Qksort(int m,int n,vector<int>&tab) {
  if (m<n) {
    int p = partition(m,n,tab);
    tri_Qksort(m,p,tab);   //recursivité,koi de mieux!
    tri_Qksort(p+1,n,tab);
  }
}
/*** menu pour le choix de fonction ***/
int Menu()
{
     int var;  
   system("cls");
cout<<endl<<"    MENU PRINCIPAL  "<<endl<<endl;
cout<<"       1 - TRI PAR BULLE          \n" <<endl;
cout<<"       2 - TRI PAR INSERTION      \n"<<endl;
cout<<"       3 - TRI  SHELL         \n" <<endl;
cout<<"       4 - TRI QUICKSORT      \n"<<endl;
cout<<"       5 - RECHERCHE DICHOTOMIQUE \n"<<endl;
cout<<endl<<" Tapez 0 pour quitter..."<<endl<<endl;
cout<<"     Choix = ";cin>>var;
  while((var<0) && (var>5))
  { 
    cout<<"Faites un choix entre 1 et 5 svp...";
    cout<<"Choix = ";cin>>var;
  } 
return var;
}
};   
/******* Programme Principal *****/
int main() 
{
tablo T;
int n,choix; //taille du tableau qu'on va utiliser
int i=0,j=0,k=0,d=0,q=0,nb,deb_tab,end_tab;
vector<int>tab_bulle,tab_shell,tab_ins,tab_Qksort,tab_dicho;
  
do
{
 srand(time(NULL));
 choix = T.Menu();
  switch(choix)
  {
    case 0: return 0;
		    break;
	
 case 1:  cout<<"TAILLE TaBLo BuLLE = ";cin>>n;
   tab_bulle.resize(n); //affecte n cases au tableau
  while(i<n)
 { 
  tab_bulle[i]=rand()%50+1;
/*je ve pa de 0 ds mon tab de + jsuis trop paresseux pr 
remplir moi mm le tab,vous le pouvez vous?pr 100 elmts ;) */
   i++;
 }
   T.tri_bulle(tab_bulle,n);cout<<endl;
     break;

case 2:  cout<<"TAILLE DU TaBLo INSERTION = ";cin>>n;
         tab_ins.resize(n);
        while(j<n)
         { 
             tab_ins[j]=rand()%50+1;
               j++;
         } 
             T.tri_insertion(tab_ins,n);cout<<endl;
             break;
case 3 : cout<<"TAILLE TaBLo SHELL = ";cin>>n;
            tab_shell.resize(n);
              for(;k<tab_shell.size();k++)
    	{  
                  tab_shell[k]=rand()%100+1;
                  k++;
	}
	T.tri_shell(tab_shell,n);
    break;
case 4: cout<<"TAILLE TaBLo QUICKSORT = ";cin>>n;
tab_Qksort.resize(n+1);//n cases pr tablo + 1 pr 1er pivot
deb_tab=-1;
end_tab=tab_Qksort.size()-1;    
     for(;q<tab_Qksort.size();q++)
     { 
        tab_Qksort[q]=rand()%50+1;
     } 
         T.tri_Qksort(deb_tab,end_tab,tab_Qksort);
         T.afficher(tab_Qksort,n);
    break;

case 5:  cout<<"TAILLE TaBLo DICHOTOMIE = ";cin>>n;
   tab_dicho.resize(n);
     while(d<tab_dicho.size())
     {   
       tab_dicho[d]=rand()%50+1;
      d++;
     }   
   T.tri_bulle(tab_dicho,n);
cout<<"Nombre a chercher par dichotomie = ";cin>>nb;
  cout<<"Indice = "<<T.dicho(tab_dicho,nb)<<endl;
  break;
 default: cout<<"Vous avez fait un mauvais choix \n";
}  
 system("pause"); // pause et attend 1 touch du clavier
}while(choix!=0);
return 0;
}

Conclusion :


J'ai eu quelques mal avec la fonction srand() car les entiers que je génère aléatoirement sont les même lorsque la taille du tableau reste la même...
Je me suis un peu documenté,mais apparemment le compilateur sous v c++ 6 n'est pas tres performant en ce qui concerne rand()...(c'est juste mon point de vue) donc si jamais qlq'1 peut m'aider sur ce point,je lui serais tres reconnaissant.

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