Tri rapide

Soyez le premier à donner votre avis sur cette source.

Snippet vu 8 604 fois - Téléchargée 29 fois

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

Ajouter un commentaire

Commentaires

geeanhell
Messages postés
4
Date d'inscription
mardi 9 décembre 2003
Statut
Membre
Dernière intervention
10 décembre 2003
-
- à quoi il te sert conio.h ?
- chouette ta fonction tri rapide ...
trasher9
Messages postés
4
Date d'inscription
mercredi 8 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2003
-
la librairie conio.h est l'abréviation de CONsole Input/Output,
elle est utile uniquement pour le getch() qui permet de stopper
l'exécution du programme jusqu'à ce que l'utilisateur presse une
touche.

Pour ceux qui se demande pourquoi j'ai une fonction tri_rapide qui
contient uniquement la fonction découpage, voici l'explication:

Dans tri_rapide, découpage devrait etre suivi d'un tri par insertion
mais ici ma taille de bloc (tbloc) est à 1 pour que le tableau soit trié entièrement. Ce n'est pas optimal car arrivé à une certaine taille de bloc, le tri par insertion est plus adapté que le tri rapide.
geeanhell
Messages postés
4
Date d'inscription
mardi 9 décembre 2003
Statut
Membre
Dernière intervention
10 décembre 2003
-
ouep, coté optimal yavait qsort aussi :D
trasher9
Messages postés
4
Date d'inscription
mercredi 8 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2003
-
lol, quick sort, ca serait pas tri rapide en français ?????????
hehe
geeanhell
Messages postés
4
Date d'inscription
mardi 9 décembre 2003
Statut
Membre
Dernière intervention
10 décembre 2003
-
exactement ...
il est ou l'intérêt de ton source ?
qsort ... voir stdlib.h

(hehe)

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.