Tri rapide

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 890 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

Messages postés
4
Date d'inscription
mercredi 8 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2003

Merci pour ces informations beozebold, il est évident que le qsort est un tri instable toutefois pour une application de ce tri sur des nombres, je pense que le qsort est suffisant. Mais ta remarque est très juste et je vais de suite aller explorer ton lien. Enfin une remarque intéressante ;o)

Trasher9
Messages postés
1
Date d'inscription
mercredi 10 septembre 2003
Statut
Membre
Dernière intervention
19 décembre 2003

Trasher9: Tout à fait d'accord avec toi sur l'importance de connaitre (voire de comprendre) les algorithmes de tri.

A ce propos je ne peux que vous recommander le Merge Sort comme algorithme de tri car celui ci à l'avantage d'être stable (à savoir si tu tries des éléments ayant plusieurs attributs (nom, prénom par exemple) d'abord sur le prénom puis sur le nom, tu trouveras, à nom identique, les prénoms classés par ordre alphabétique). Ce qui n'est pas le cas avec le Quick Sort. Malheureusement il semble que le QSort ait meilleure presse que son cousin le Merge Sort (ce que je regrette) alors parlez-en autour de vous, faites-en la promotion auprès de vos professeurs d'informatique :)

Pour une explication complète (mais en anglais) sur le Merge Sort,je vous conseille l'adresse suivante : http://www.cs.toronto.edu/~neto/teaching/238/16/mergesort.html

il y a même un applet Java pour expliquer le fonctionnement.


Bien à vous

BeoZeBold
Messages postés
4
Date d'inscription
mercredi 8 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2003

et bien il existe un domaine qui se nomme algorithme, il est bien évident que tu peux très bien utiliser niaisement les fonctions mises à disposition, mais si tu a envie de savoir qu'est ce que ce tri fait vraiment, c'est bien mieux de le voir sous cette forme. enfin c'est mon avis. pour programmer, on est bien obligé de savoir ce qui se passe derrière.
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)
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
Afficher les 8 commentaires

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.