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.
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.
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
- Tri rapide en c
- Tri rapide c - Meilleures réponses
- Tri rapide - Meilleures réponses
- Tri rapide python - Guide
- Tri rapide c++ - Guide
- Tri rapide pascal - Guide
- Visual Basic / VB.NET : Tri rapide (quicksort) d'un tableau de chaînes de caractères - - Guide
- Java : Tri rapide tout type - CodeS SourceS - Guide
Commentaires
- Messages postés
- 4
- Date d'inscription
- mardi 9 décembre 2003
- Statut
- Membre
- Dernière intervention
- 10 décembre 2003
-- chouette ta fonction tri rapide ...
- Messages postés
- 4
- Date d'inscription
- mercredi 8 octobre 2003
- Statut
- Membre
- Dernière intervention
- 21 décembre 2003
-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.
- Messages postés
- 4
- Date d'inscription
- mardi 9 décembre 2003
- Statut
- Membre
- Dernière intervention
- 10 décembre 2003
-- Messages postés
- 4
- Date d'inscription
- mercredi 8 octobre 2003
- Statut
- Membre
- Dernière intervention
- 21 décembre 2003
-hehe
- Messages postés
- 4
- Date d'inscription
- mardi 9 décembre 2003
- Statut
- Membre
- Dernière intervention
- 10 décembre 2003
-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.