Tri rapide

Commenter

Contenu du snippet

voici un tri rapide qui permet de trier un tableau.

Source / Exemple : 


#include <stdio.h>
#include <conio.h>

void exploration(int*,int,int,int&);
void choix_pivot(int*,int,int);
void decoupage(int*,int,int);
void tri_rapide(int*,int,int);

void main()
{
   int g=0;
   int d=19;
   int T[20]={0,12,14,2,56,30,5,8,35,11,89,47,23,44,3,55,32,1,34,67};

   printf("\nTableau non trie :\n\n");
   for(int i=0;i<=d;i++) printf("%4d", T[i]);
   printf("\n\n");
   tri_rapide(T,g,d);
   printf("\n\nTableau trie :\n\n");
   for(int i=0;i<=d;i++) printf("%4d", T[i]);
   getch();
}

void exploration(int *T,int g,int d,int &place)
{
   int temp;
   int i=g;
   int j=d+1;
   int pivot=T[g];
   while(i<j)
   {
      do
      {
           i+=1;
      }
      while(T[i]<pivot);
      
      do
      {
           j-=1;
      }
      while(T[j]>pivot);

      temp=T[i];
      T[i]=T[j];
      T[j]=temp;
   }
   if(i>j)
   {
      temp=T[i];
      T[i]=T[j];
      T[j]=temp;
   }
   i-=1;
   place=i;
   temp=T[place];
   T[place]=T[g];
   T[g]=temp;
}
void choix_pivot(int *T,int g,int d)
{
   int indpivot;
   int temp;
	int milieu=(g+d)/2;
   if(T[g]<=T[milieu])
   {
      if(T[milieu]<=T[d]) indpivot=milieu;
      else
      {
         if(T[d]<=T[g]) indpivot=g;
         else indpivot=d;
      }
   }
   else
   {
      if(T[d]<=T[milieu]) indpivot=milieu;
      else
      {
           if(T[g]<=T[d]) indpivot=g;
           else indpivot=d;
      }
   }
   temp=T[indpivot];
   T[indpivot]=T[g];
   T[g]=temp;
}
void decoupage(int *T,int g,int d)
{
   int place;
   int tbloc=1;
   if((d-g)>=tbloc)
   {
      choix_pivot(T,g,d);
      exploration(T,g,d,place);
      if((place-g)>(d-place))
      {
           decoupage(T,place+1,d);
           decoupage(T,g,place-1);
      }
      else
      {
            decoupage(T,g,place-1);
            decoupage(T,place+1,d);
      }
   }
}

void tri_rapide(int *T,int g,int d)
{
     decoupage(T,g,d);
}

Conclusion :


d représente la droite,g la gauche.
le pivot est l'élément que l'on compare pour séparer les éléments plus petits et plus grands.
Si vous avez des questions, laissez un message.

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.