QuickSort : liste chaînée

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.

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 */
liste 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)<pivot)
            {
                compt=compt->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;
}

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.

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);
    }
}

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)<pivot)
            {
                compt=compt->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 ^^)

++

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);
        }
    }
}