vegeta07
Messages postés3Date d'inscriptionmardi 7 novembre 2000StatutMembreDernière intervention 6 juin 2005
-
6 juin 2005 à 17:14
vdust
Messages postés43Date d'inscriptionjeudi 16 décembre 2004StatutMembreDernière intervention14 mars 2007
-
7 juin 2005 à 00:17
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.
vdust
Messages postés43Date d'inscriptionjeudi 16 décembre 2004StatutMembreDernière intervention14 mars 2007 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 --
Vous n’avez pas trouvé la réponse que vous recherchez ?
vdust
Messages postés43Date d'inscriptionjeudi 16 décembre 2004StatutMembreDernière intervention14 mars 2007 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));