Tri rapide
Soyez le premier à donner votre avis sur cette source.
Snippet vu 13 105 fois - Téléchargée 31 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
- Trie rapide en c - Meilleures réponses
- Tri rapide python - Guide
- Tri rapide c# - Guide
- Visual Basic / VB.NET : Tri rapide (quicksort) d'un tableau de chaînes de caractères - - Guide
- Delphi / Pascal : Méthode de tri rapide ( quick-sort ) - CodeS SourceS - Guide
- C / C++ / C++.NET : Tri rapide (quicksort) - CodeS SourceS - Guide
21 déc. 2003 à 01:57
Trasher9
19 déc. 2003 à 19:52
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
11 déc. 2003 à 00:36
10 déc. 2003 à 19:03
il est ou l'intérêt de ton source ?
qsort ... voir stdlib.h
(hehe)
10 déc. 2003 à 00:30
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.