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

3/5 (9 avis)

Snippet vu 6 276 fois - Téléchargée 35 fois

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

Ajouter un commentaire Commentaires
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

euhm, chaque fois que tu appels srand, tu réinitialises le seed, et c'est le seed qui détermine la liste des nombres qui vont sortir "pseudo-aléatoirement".

#include
#include <ctime>
#include <cstdlib>
using namespace std;

int main(int argc, char **argv)
{
srand(time(NULL));
cout << rand() << endl;
srand(time(NULL));
cout << rand() << endl;
srand(time(NULL));
cout << rand() << endl;
srand(time(NULL));
cout << rand() << endl;

cin.get();
return 0;
}


ceci sort 4 fois le même chiffre car l'heure n'aura pas changé entre les appels à srand -> le seed est le même -> la liste de nombres est la même -> le premier est tjs le même! cqfd. il faut impérativement n'appeler srand qu'une seule fois!
Messages postés
30
Date d'inscription
samedi 4 décembre 2004
Statut
Membre
Dernière intervention
2 avril 2008

oué en effet,ça ne change rien de mettre srand() juste au debut,je pense plutot que c'est le compil de v c++6 qui n'est pas tres puissant... sous linux j'ai de meilleurs resultats...
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
28
srand() serait aussi bien hors du 'do', direct dans le main() en 1ere instruction, mais bon doit pas etre dramatique.
Messages postés
30
Date d'inscription
samedi 4 décembre 2004
Statut
Membre
Dernière intervention
2 avril 2008

ok je vais tenir compte de tes remarques Brunews,après tout je suis là pour apprendre et donc je te remercie.Mais par contre il me semble avoir mis le srand() une seule fois au debut de mon mail,si c'est pas comme ça,alors je reste à l'ecoute...merci
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
28

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.