jibax Le 26/05/2003 à 11:07 bon j'suis en galère la, car je dois faire des algo de tri qui marche pour tout type de donnée (int,char,string...) à la manière de qsort...
alors si quelqu'un peut me dire ou trouver l'algo en C de la fonction qsort (si ca existe?) ce serait cool...
de plus je voudrais savoir si c'est possible de déclarer des variables dans des if{}
et ainsi de déclarer une variable, de type differnet selon les conditions (bon si personne comprend ce que j'essaie de dire c'est po grave...)
jibax Le 26/05/2003 à 11:43 en fait, je me demandait aussi ou sont stockée les libs et comment?
ahhhhhhhhhh je lé fé ça
mais alors me souvien pu ou est l'algo.....................
Il m'a fait trop de mal pour en dire du bien, il ma fait trop de bien pour en dire du mal... Quant à moi, je ne vaut rien...
La nostalgie C’est tout ce que je ne t’ai jamais dit C’est tout ce que je n’ai jamais entendu De toi C’est tout l’infini A côté duquel je suis passée Sans même le pressentir En l’ignorant totalement Alors qu’il y avait des signes partout Pour chacun de nous
[url]savon de toulon[/url]
http://www.monblognote.com
http://photographies.julyd.free.fr/galeriephotos
25.10.02\
Spipu Le 27/05/2003 à 12:26 fonction QuickSort :
//----# 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); }
}
pour l'utiliser, mets tes données ds PointFichier de dimension NbFichier
et fait QuickSort(0, NbFichier-1);
il me met environ 3 sec pour trier 1000000 valeurs, sur un XP2400+
jibax Le 27/05/2003 à 13:01 bon en fait l'algo pour trier des nombres c'etait pas le probleme... y'en a partout sur internet
ce que je voulais c'est celui équivalent à celui contenu dans stdlib.h et qui permet de travailler sur n'importe quel type: int, long, char, et meme des string...
sa déclaration c'est
void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
et apparement le prof nous a dit d'ignorer le truc avec userentry
bon de plus pour typeof je peux pas l'utilisé c'est pas c ansi...
donc apparement faut utiliser un type void*, mais comment faire pour comparer, creer des variables locales...
jibax Le 27/05/2003 à 13:39 bah de maniere pratique quand du as un vecteur de char
que tu déclare en void * dans l'appelle de la fonction de tri
comment tu fait pour comparer à l'interieur de la fonction deux elements du vecteur en connaissant la taille (width=sizeof(char)) d'un élément du vecteur.
de meme si 'tutilise un tampon dans ta fonction est ce que tu le déclare en void?et comment fait tu pour lui donner une valeur?
bon je sais pas si j'ai été plus clair? en gros je veux réaliser une fonction analogue a qsort (qui marche avec tout type de tableau(regardez la déclaration de qsort)
jibax Le 27/05/2003 à 13:46 bon , voila la doc de borland sur qsort
Syntax
#include <stdlib.h>
void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
Description
Sorts using the quicksort algorithm.
qsort is an implementation of the "median of three" variant of the quicksort algorithm. qsort sorts the entries in a table by repeatedly calling the user-defined comparison function pointed to by fcmp.
base points to the base (0th element) of the table to be sorted.
nelem is the number of entries in the table.
width is the size of each entry in the table, in bytes.
fcmp, the comparison function, must be used with the _USERENTRY calling convention.
fcmp accepts two arguments, elem1 and elem2, each a pointer to an entry in the table. The comparison function compares each of the pointed-to items (*elem1 and *elem2), and returns an integer based on the result of the comparison.
*elem1 < *elem2 fcmp returns an integer < 0
*elem1 == *elem2 fcmp returns 0
*elem1 > *elem2 fcmp returns an integer > 0
In the comparison, the less-than symbol (< ) means the left element should appear before the right element in the final, sorted sequence. Similarly, the greater-than (> ) symbol means the left element should appear after the right element in the final, sorted sequence.
Return Value
None.
jibax Le 28/05/2003 à 12:19 bon, y'a plus personne pour me répondre?
jibax Le 02/06/2003 à 13:10 merci de vos reponses bien que l'algo je vous ai dit qu'il fallait qu'il marche a la fois pour des nombre, des char et des str a la lmaniere de qsort, enfin si personne veut comprendre...
mais bon, j'ai truové une solution en passant par des void* puis en utilisant
memcpy et des memcmp avec des (char*)tab+i*width...et ca a l'air de marcher
Sinon Kevin merci de ta reponse super constructive mais sache que ca fait deux semaines que je cherche et que je demandais de l'aide sur un point precis qui n'est qu'une partie de mon projet et pas qu'on me ponde un truc tout fait.
jibax Le 02/06/2003 à 18:13 ouais c'est vrai, merci nitro, qui m'a donné le début de la solution
si ça vaut encore le coup.....
// 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.
#define CMP(a,b) (*cp)(pt[a],pt[b]) // macro pour faciliter l'écriture du code
#define CMPp(a,p) (*cp)(pt[a],p) // idem
// 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]);
*/
Il m'a fait trop de mal pour en dire du bien, il ma fait trop de bien pour en dire du mal... Quant à moi, je ne vaut rien...
La nostalgie C’est tout ce que je ne t’ai jamais dit C’est tout ce que je n’ai jamais entendu De toi C’est tout l’infini A côté duquel je suis passée Sans même le pressentir En l’ignorant totalement Alors qu’il y avait des signes partout Pour chacun de nous
[url]savon de toulon[/url]
http://www.monblognote.com
http://photographies.julyd.free.fr/galeriephotos
25.10.02\
aRf, goto pas rulez ... c'est vraiment horrible de voir cela dans un code pareil !
Y-en a marre des fanatiques anti-goto! goto est une instruction utile comme les autres! Si tu n'aimes pas, personne ne t'oblige à l'utiliser, mais ne gueule pas dessus à ceux qui trouvent ça pratique!
Uther Le 03/06/2003 à 15:22 goto est une instruction qu'il faut utiliser avec parcimonie si on veut garder du code propre.
Bah, évidemment, je ne propose pas d'utiliser:
int i=0;
label1:
if(i>=8) goto label2;
...
i++;
goto label1;
label2:;
quand on pourrait utiliser un simple:
for (int i=0;i<8;i++) {
...
}
(dans ce cas, je suis d'accord que le premier exemple est codé n'importe comment) mais il y a des fois où le goto est la représentation la plus logique et donc la plus lisible. Dans ces cas, essayer de les transformer en des boucles "structurées" donnerait du code moins lisible, pas du code plus lisible.
C'est rare que le goto soit indispensable, uniquement dans le cas de plusieurs boucles imbriquées ...
Uther Le 03/06/2003 à 17:09 dans ces cas la oui mais la majorité du temps on peu s'en passer
on _peut_, oui...
mais fo admettre que ca arrange bien les choses, qd on l'utilisise judicieusement
