qsort, me semble que c'est diviser pour mieux reigner ... nan ?
Si oué, ca fait des tas que tu divises etc. C'est donc récursif ...
nitro
a écrit : typeof n'est pas standard.
) l'accepte.
squale92
a écrit : Cela dit, la fonction qsort des librairies C n'est pas obligée d'utiliser un QuickSort... Elle utilise en general ce qui correspond le mieux a l'architecture de la machine. (sous TIGCC, par exemple, il me semble que ce n'est pas un QuickSort (je ne suis pas certain, cela dit))
La raison pour laquelle on utilise le Shell Sort est que le code prend moins de place (et que Zeljko n'a mesuré aucune différence de vitesse visible avec les tableaux de petite taille généralement utilisés sur une calculatrice). 
//----# QuickSort relatif à la série de points #----
void LAMBDA::QuickSort(long Kmin, long Kmax)
{
long i, k;
double xi;
i=Kmin; xi=PointFichier[i];
for (k=Kmin+1;k<=Kmax;k++)
{
if (PointFichier[k]<xi)
{
PointFichier[i]=PointFichier[k];
PointFichier[k]=PointFichier[i+1];
PointFichier[i+1]=xi;
i++;
}
}
if (i>Kmin+1) { QuickSort(Kmin,i-1); }
if (i<Kmax-1) { QuickSort(i+1,Kmax); }
}
(peut-être pas envie de comprendre ...)
jibax
a écrit : bon, y'a plus personne pour me répondre?
mais bon, j'ai truové une solution en passant par des void*
// Universite LYON I - IUT A - Informatique 1ère année
//
// Programmation C++
//
// Module trirapide.cpp
//
// Contient la fonction trirapide() qui effectue une tri indirect universel
// par le méthode "quicksort" de HOARE (1962) améliorée.
//
// L'indirection est obtenue au travers d'un tableau de pointeurs sur les
// éléments à trier qui eux sont situés n'importe où (pas nécessairement
// dans un tableau) en mémoire. Ceux-ci ne sont pas déplacés mais le tableau
// de pointeurs sera réorganisé.
//
// L'universalité est obtenue par la fourniture d'un pointeur sur une fonction
// de comparaison ayant comme arguments des pointeurs non typés.
// En programmation objet vous verrez une autre approche par les "templates"
// qui n'évitent pas les fonctions de comparaisons remplacées par la surcharge
// des opérateurs de comparaisons et qui dupliquent le code autant de fois que
// des types (ou classes) nouvelles seront utilisées.
//
// Ce module tout à fait opérationnel et écrit dans une optique "professionnelle"
// illustre quelques aspects du cours, notamment :
//
// - Les pointeurs sur données, notation indicée, tableaux de pointeurs, pointeurs
// non typés ...
// - Les pointeurs sur fonctions
// - Les macros
// - La directive static qui appliquée aux entités globales les rendent
// "privées" pour le module et qui appliquée aux variables locales
// interdisent leur installation dans la pile.
// - La stratégie d'utilisation minimale de la pile en environnement récursif.
// - L'utilisation intelligente (et contrôlée) de l'instruction goto.
// Il est à noter que WIRTH, le père de la programmation structurée et du
// langage PASCAL a introduit l'instruction GOTO dans son langage pour un usage
// limité aux cas où la programmation en serait efficacement simplifiée !
//
// On pourra comparer avec la fonction qsort() de la bibliothèque C qui effectue
// aussi un tri universel.
static int (*cp)(void *,void *); // pointeur sur fonction de comparaison
// placé en global pour ne pas encombrer la pile
// lors de la récursion.
// static pour que l'identificateur cp
// reste local au module
static void **pt; // copie en global du pointeur sur le tableau
// des pointeurs sur les éléments à trier
// Même stratégie que pour cp.
// fonction récursive de la méthose "quicksort" avec diverses améliorations
// static car locale au module
static void qsort(int l, int r) // les arguments l et r sont empiles
{
static void *pv; // pointeur sur valeur de séparation : non empilé
static int i; // indice parcours depuis la gauche : non empilé
int j; // indice parcours depuis la droite : empilé car doit
// être restitué en issue de récursion
// A chaque appel récursif ne sont donc empilés que
// - les 3 entiers l, r et j
// - l'adresse de retour et la sauvegarde du registre EBP (cas des
// processeurs INTEL)
if(l-r > 100) { // sinon on triera le sous-tableau par SHELL-METZNER
// la valeur de séparation sera la médiane entre les éléments de
// positions l, (l+r)/2 et r pour éviter le "mauvais cas" de quicksort
j=(l+r)/2;
if(CMP(l,r) > 0) {
if(CMP(l,j) < 0) j=l;
}
else {
if(CMP(r,j) < 0) j=r;
}
pv=pt[j]; pt[j]=pt[r]; // pt[r]=pv; affectation inutile
// le pointeur sur valeur de séparation est en r
// Partitionnement
// Existe-t-il une formulation plus claire et efficace ?
i=l-1; j=r;
for(;;) {
do {
if(++i == j) goto fini;
} while(CMPp(i,pv) < 0);
pt[j]=pt[i];
do {
if(--j == i) goto fini;
} while(CMPp(j,pv) >= 0);
pt[i]=pt[j];
}
fini: pt[j]=pv;
// maintenant les pointeurs pt[k] avec l <= k < j pointent sur des
// éléments "inférieurs" strictement aux éléments pointés par
// pt[m] avec j <= m <= r
// on se ramène au problème précédent par recursions
qsort(l,j-1); // tri de la partie gauche
qsort(j+1,r); // tri de la partie droite
// j-1 et j+1 car l'élément j est "en place"
}
else { // pas de récursion pour les "petits sous-tableaux"
static int n; // nombre d'éléments du sous-tableau
static void **qt; // pointeur sur le sous-tableau à trier
static int pas; // pour SHELL-METZNER
if((n=r-l+1) < 2) return; // car rien à faire
qt=pt+r; // pour pouvoir utiliser la notation qt[i]
// avec comme premier élément qt[0]
pas = n < 10 ? 1 : n/2; // Méthode de tri par insertion si n < 10
do {
for(i=pas; i<n; i++) {
pv=qt[i];
for(j=i-pas; j >= 0 && CMPp(j,pv) > 0; j-=pas) qt[j+pas]=qt[j];
qt[j+pas]=pv;
}
} while(pas/=2); // ou while((pas/=2) != 0)
}
}
// Fonction d'appel qui sera la seule connue en dehors de ce module
void trirapide(void *p[], int n, int (*cmp)(void *,void *))
{
// préparation de l'environnement récursif
pt=p;
cp=cmp;
// lancement effectif de la fonction récursive
qsort(0,n-1);
}
// Exemple d'utilisation :
/*
char *pmots[1000]; // tableau de pointeurs sur des chaines de caractères
// ces chaines ne seront pas déplacées.
int nmots; // nombre utile de mots <= 1000
// nmots et pmots supposés initialisés
trirapide(pmots,nmots,strcmp); // strcmp() de la bibliothèque C
// on a effectué un tri indirect : voici par exemple un affichage ordonné des mots
for(i=0; i<nmots; i++) printf("%-s\n",pmots[i]);
*/
C'est rare que le goto soit indispensable, uniquement dans le cas de plusieurs boucles imbriquées
