QuickSort : liste chaînée
vegeta07
Messages postés
3
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
6 juin 2005
-
6 juin 2005 à 17:14
vdust Messages postés 43 Date d'inscription jeudi 16 décembre 2004 Statut Membre Dernière intervention 14 mars 2007 - 7 juin 2005 à 00:17
vdust Messages postés 43 Date d'inscription jeudi 16 décembre 2004 Statut Membre Dernière intervention 14 mars 2007 - 7 juin 2005 à 00:17
A voir également:
- Quicksort c
- C quicksort - Meilleures réponses
- Quicksort en c - Meilleures réponses
- Quicksort sans récurisivité ( appel a sa propre fonction) en pur C - Forum C
- Tri par Sélection,Tri par Insertion, Tri Rapide (QuickSort), Tri à Bulles, Tri p - Forum Delphi / Pascal
5 réponses
vegeta07
Messages postés
3
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
6 juin 2005
6 juin 2005 à 17:19
6 juin 2005 à 17:19
Salut,
Je souhaite réaliser le tri QuickSort (récursif) sur une liste simplement chaînée.
Mais j'ai un probleme sur la recursivité je pense.
Si quelqu'un a le temps de regarder le code (peu compliqué), j'aimerais avoir votre avis ou au mieux votre solution.
Merci.
avec le code c 'est mieux.
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud
{
int valeur;
struct noeud *suivant;
} element;
typedef element *liste;
int vide(liste lc)
{
return (lc= =NULL);
}
/* retourne un pointeur sur le dernier element de la liste */
l iste pointeur_fin(liste lc)
{
liste tmp;
tmp =(liste)malloc(sizeof(element));
tmp= lc;
if(!vide(lc) && !vide(lc->suivant))
{
while((tmp->suivant)!=NULL)
{
tmp=tmp->suivant;
}
return tmp;
}
return tmp;
}
liste ajoutFIN(liste l, int val)
{
liste tmp,nouv;
tmp =l;
nouv= (liste)malloc(sizeof(element));
nouv->suivant=NULL;
nouv->valeur=val;
if(l==NULL)
{
l=nouv;
}
else
{
while(!vide(tmp->suivant))
{
tmp=tmp->suivant;
}
tmp->suivant=nouv;
}
return l;
}
liste creation(liste lc)
{
int nbval,val,i =0;
printf("\nEntrez le nombre de valeur a saisir : ");
scanf("%d",&nbval);
while(i<nbval)
{
printf("\nEntrez la valeur %d : ",i+1);
scanf("%d",&val);
lc= ajoutFIN(lc,val);
i++;
}
return lc;
}
void afficher(liste lc)
{
printf("\n\nListe chainee obtenue : \n\n");
while(!vide(lc))
{
printf("%3d",lc->valeur);
lc =lc->suivant;
}
}
/* fonction permettant d'acceder au precedent d'un element */
liste precedent(liste lc, int val)
{
liste tmp,tmp1;
tmp= lc;
tmp1=tmp->suivant;
while((tmp1->valeur)!=val)
{
tmp1=tmp1->suivant;
tmp=tmp->suivant;
}
return tmp;
}
/* fonction permettant de partitionner la liste :
les valeurs superieur au pivot sont a doite et inversement*/
liste partition (liste lc,liste debut, liste fin)
{
int permu;
int pivot =debut->valeur;
liste compt= debut;
liste tmp=debut->suivant;
if(!vide(debut))
{
while((tmp)!=(fin->suivant))
{
if((tmp->valeur)suivant;
permu=tmp->valeur;
tmp->valeur=compt->valeur;
compt->valeur=permu;
}
tmp=tmp->suivant;
}
permu=debut->valeur;
debut->valeur=compt->valeur;
compt->valeur=permu;
return compt;
}
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
if((debut->valeur)<(fin->valeur))
{
liste
pivot =partition(lc,debut,fin);
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
int main(void)
{
liste lc=NULL;
liste debut=NULL;
liste fin=NULL;
lc=creation(lc);
afficher(lc);
debut=lc;
fin=pointeur_fin(lc);
quicksort(lc,debut,fin);
afficher(lc);
return 0;
}
Je souhaite réaliser le tri QuickSort (récursif) sur une liste simplement chaînée.
Mais j'ai un probleme sur la recursivité je pense.
Si quelqu'un a le temps de regarder le code (peu compliqué), j'aimerais avoir votre avis ou au mieux votre solution.
Merci.
avec le code c 'est mieux.
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud
{
int valeur;
struct noeud *suivant;
} element;
typedef element *liste;
int vide(liste lc)
{
return (lc= =NULL);
}
/* retourne un pointeur sur le dernier element de la liste */
l iste pointeur_fin(liste lc)
{
liste tmp;
tmp =(liste)malloc(sizeof(element));
tmp= lc;
if(!vide(lc) && !vide(lc->suivant))
{
while((tmp->suivant)!=NULL)
{
tmp=tmp->suivant;
}
return tmp;
}
return tmp;
}
liste ajoutFIN(liste l, int val)
{
liste tmp,nouv;
tmp =l;
nouv= (liste)malloc(sizeof(element));
nouv->suivant=NULL;
nouv->valeur=val;
if(l==NULL)
{
l=nouv;
}
else
{
while(!vide(tmp->suivant))
{
tmp=tmp->suivant;
}
tmp->suivant=nouv;
}
return l;
}
liste creation(liste lc)
{
int nbval,val,i =0;
printf("\nEntrez le nombre de valeur a saisir : ");
scanf("%d",&nbval);
while(i<nbval)
{
printf("\nEntrez la valeur %d : ",i+1);
scanf("%d",&val);
lc= ajoutFIN(lc,val);
i++;
}
return lc;
}
void afficher(liste lc)
{
printf("\n\nListe chainee obtenue : \n\n");
while(!vide(lc))
{
printf("%3d",lc->valeur);
lc =lc->suivant;
}
}
/* fonction permettant d'acceder au precedent d'un element */
liste precedent(liste lc, int val)
{
liste tmp,tmp1;
tmp= lc;
tmp1=tmp->suivant;
while((tmp1->valeur)!=val)
{
tmp1=tmp1->suivant;
tmp=tmp->suivant;
}
return tmp;
}
/* fonction permettant de partitionner la liste :
les valeurs superieur au pivot sont a doite et inversement*/
liste partition (liste lc,liste debut, liste fin)
{
int permu;
int pivot =debut->valeur;
liste compt= debut;
liste tmp=debut->suivant;
if(!vide(debut))
{
while((tmp)!=(fin->suivant))
{
if((tmp->valeur)suivant;
permu=tmp->valeur;
tmp->valeur=compt->valeur;
compt->valeur=permu;
}
tmp=tmp->suivant;
}
permu=debut->valeur;
debut->valeur=compt->valeur;
compt->valeur=permu;
return compt;
}
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
if((debut->valeur)<(fin->valeur))
{
liste
pivot =partition(lc,debut,fin);
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
int main(void)
{
liste lc=NULL;
liste debut=NULL;
liste fin=NULL;
lc=creation(lc);
afficher(lc);
debut=lc;
fin=pointeur_fin(lc);
quicksort(lc,debut,fin);
afficher(lc);
return 0;
}
darfeuille
Messages postés
63
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
25 juillet 2005
6 juin 2005 à 17:28
6 juin 2005 à 17:28
j'ai pas le temps de tout verifier, mais je vois que tu fais
int pivot=debut->valeur;
liste compt=debut;
liste tmp=debut->suivant;
if(!vide(debut))
si debut == Null (ce que tu teste apres par if(!vide(debut)) justement)
pivot = debut->valeur va te faire des erreurs
Change ca, ca marchera peut etre apres, sinon rien ne me saute aux yeux.
int pivot=debut->valeur;
liste compt=debut;
liste tmp=debut->suivant;
if(!vide(debut))
si debut == Null (ce que tu teste apres par if(!vide(debut)) justement)
pivot = debut->valeur va te faire des erreurs
Change ca, ca marchera peut etre apres, sinon rien ne me saute aux yeux.
vegeta07
Messages postés
3
Date d'inscription
mardi 7 novembre 2000
Statut
Membre
Dernière intervention
6 juin 2005
6 juin 2005 à 17:47
6 juin 2005 à 17:47
Merci pour la remarque, tu as tout à fait raison.
Mais je crois surtout que c'est ma condition d'arret qui est mauvaise.
Avec ta modif, j'ai ensuite essayé de changer cette condition en
comparant les positions des pointeurs "debut" et "fin" (comme si
c'était un tableau).
Et le prog ne fonctionne toujours pas... malédiction
/* donne le rand d'un element comme dans un tableau*/
int compteur(liste lc, liste elem)
{
liste tmp= lc;
int cpt=0;
if (!vide(lc))
{
while(!vide(tmp) && (tmp->valeur)!=(elem->valeur))
{
cpt++;
tmp=tmp->suivant;
}
return cpt;
}
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
liste pivot =partition(lc,debut,fin);
/* modification de la condition*/
if((compteur(lc,debut))<(compteur(lc,fin)))
{
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
Mais je crois surtout que c'est ma condition d'arret qui est mauvaise.
Avec ta modif, j'ai ensuite essayé de changer cette condition en
comparant les positions des pointeurs "debut" et "fin" (comme si
c'était un tableau).
Et le prog ne fonctionne toujours pas... malédiction
/* donne le rand d'un element comme dans un tableau*/
int compteur(liste lc, liste elem)
{
liste tmp= lc;
int cpt=0;
if (!vide(lc))
{
while(!vide(tmp) && (tmp->valeur)!=(elem->valeur))
{
cpt++;
tmp=tmp->suivant;
}
return cpt;
}
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
liste pivot =partition(lc,debut,fin);
/* modification de la condition*/
if((compteur(lc,debut))<(compteur(lc,fin)))
{
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
vdust
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007
7 juin 2005 à 00:04
7 juin 2005 à 00:04
Pas besoin d'allourdir ton code avec ta
fonction compteur. Juste quelques modifications, en paufinant le
contrôle de la terminaison de l'algorithme :
liste partition (liste lc, liste debut, liste fin)
{
int permu;
int pivot; //= debut->valeur; // on le définira plus tard
liste compt = debut; // ici, on laisse. Si NULL pas grave
liste tmp; //=debut->suivant; // et re ^^
if (!vide(debut))
{
//on initialise tout maintenant qu'on peut
//de manière sûre
pivot = debut->valeur;
compt = debut
tmp = debut->suivant;
while ((tmp)! =(fin->suivant))
{
if((tmp->valeur)suivant;
permu= tmp->valeur;
tmp->valeur=compt->valeur;
compt->valeur=permu;
}
tmp=tmp->suivant;
}
permu=debut->valeur;
debut->valeur=compt->valeur;
compt->valeur=permu;
// return compt; // ne traite que le cas ou 'debut' non null
}
return compt; // retourne un élément lorsque 'debut' est non null, NULL sinon.
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
if ((debut->valeur)<(fin->valeur))
{
liste pivot =partition(lc,debut,fin);
if(!vide(pivot)){ // si pivot vide, rien à faire
// c'est la terminaison
attendue
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
}
Bien qu'en apparence, cet algorithme pour les listes chaînées simples
ressemble à un Quicksort, elle n'en est pas moins très éloignée en
terme de complexité (temps d'execution), en raison de la fonction
'precedent' qui nécessite à chaque fois de reparcourir la liste depuis
le début, ce qui est catastrophique dans le cas de très grandes listes.
Je ne sais pas si tu as l'intention de l'utiliser dans un programme
quelconque, mais je ne t'y encouragerais absolument pas. Mieux vaut
dans ce cas utiliser une liste doublement chaînée qui donne de bien
meilleurs résultats (l'élément précédent est obtenu instantanément par
exemple).
J'espère cependant que l'algorithme fonctionne maintenant (je n'ai vérifié que sur le papier ^^)
++
-- Virtual Dust --
fonction compteur. Juste quelques modifications, en paufinant le
contrôle de la terminaison de l'algorithme :
liste partition (liste lc, liste debut, liste fin)
{
int permu;
int pivot; //= debut->valeur; // on le définira plus tard
liste compt = debut; // ici, on laisse. Si NULL pas grave
liste tmp; //=debut->suivant; // et re ^^
if (!vide(debut))
{
//on initialise tout maintenant qu'on peut
//de manière sûre
pivot = debut->valeur;
compt = debut
tmp = debut->suivant;
while ((tmp)! =(fin->suivant))
{
if((tmp->valeur)suivant;
permu= tmp->valeur;
tmp->valeur=compt->valeur;
compt->valeur=permu;
}
tmp=tmp->suivant;
}
permu=debut->valeur;
debut->valeur=compt->valeur;
compt->valeur=permu;
// return compt; // ne traite que le cas ou 'debut' non null
}
return compt; // retourne un élément lorsque 'debut' est non null, NULL sinon.
}
/* Fonction supposée réaliser le tri ... */
void quicksort(liste lc, liste debut, liste fin)
{
if ((debut->valeur)<(fin->valeur))
{
liste pivot =partition(lc,debut,fin);
if(!vide(pivot)){ // si pivot vide, rien à faire
// c'est la terminaison
attendue
quicksort(lc,debut,precedent(lc,pivot->valeur));
quicksort(lc,(pivot->suivant),fin);
}
}
}
Bien qu'en apparence, cet algorithme pour les listes chaînées simples
ressemble à un Quicksort, elle n'en est pas moins très éloignée en
terme de complexité (temps d'execution), en raison de la fonction
'precedent' qui nécessite à chaque fois de reparcourir la liste depuis
le début, ce qui est catastrophique dans le cas de très grandes listes.
Je ne sais pas si tu as l'intention de l'utiliser dans un programme
quelconque, mais je ne t'y encouragerais absolument pas. Mieux vaut
dans ce cas utiliser une liste doublement chaînée qui donne de bien
meilleurs résultats (l'élément précédent est obtenu instantanément par
exemple).
J'espère cependant que l'algorithme fonctionne maintenant (je n'ai vérifié que sur le papier ^^)
++
-- Virtual Dust --
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
vdust
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007
7 juin 2005 à 00:17
7 juin 2005 à 00:17
Petite erreur dans mon précédent message, dans la fonction quicksort. Sur la condition if(!vide(pivot))... j'ai oublié un cas
void quicksort(liste lc, liste debut, liste fin)
{
if((debut->valeur)<(fin->valeur))
{
liste pivot=partition(lc,debut,fin);
if(!vide(pivot)){ // si pivot vide, rien à faire
// c'est la terminaison
attendue
quicksort(lc,debut,precedent(lc,pivot->valeur));
if(!vide(pivot->suivant))
quicksort(lc,(pivot->suivant),fin);
}
}
}
-- Virtual Dust --
void quicksort(liste lc, liste debut, liste fin)
{
if((debut->valeur)<(fin->valeur))
{
liste pivot=partition(lc,debut,fin);
if(!vide(pivot)){ // si pivot vide, rien à faire
// c'est la terminaison
attendue
quicksort(lc,debut,precedent(lc,pivot->valeur));
if(!vide(pivot->suivant))
quicksort(lc,(pivot->suivant),fin);
}
}
}
-- Virtual Dust --
