1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Vienne (Limousin)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2017
    Messages : 4
    Points : 14
    Points
    14

    Par défaut Tri à bulle avec liste chainée

    Quelq'un peut m'aider?

    Avec les tableaux, il suffit d'intervertir les elements successifs tant qu' il existe deux elements consécutifs décroissant, avec un boolean pour arrêter la boucle.
    Mais en liste chainée, on ne peut (veut?) pas intervertir deux elements.

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Bonjour

    on ne peut (veut?) pas intervertir deux elements.
    C'est le principe du tri. Si tu n'intervertis rien, tu ne tries pas.

    Le cas de la liste chaînée est particulièrement délicat et pédagogique car il faux briser les chaînes, ne perdre aucune référence, intervertir et ré-enchaîner.

    Bonne chance
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  3. #3
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 731
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 731
    Points : 127 664
    Points
    127 664

    Par défaut



    Pour ajouter un élément qui manque probablement : tu as besoin de deux éléments consécutifs de la liste pour les comparer, mais aussi de l'élément précédent (pour changer son pointeur pour l'élément qui le suit). Ça fait un peu de chipotage .
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Membre régulier
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    103
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 103
    Points : 93
    Points
    93

    Par défaut

    Bah, mets la liste en tableau, trie et remets en chaîne

  5. #5
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 822
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 822
    Points : 6 228
    Points
    6 228

    Par défaut

    Ou alors insérer dans l'ordre au moment de la création ...
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  6. #6
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Citation Envoyé par Trap D Voir le message
    Ou alors insérer dans l'ordre au moment de la création ...
    Cette description est celle d'un tri par insertion. Pas un tri à remontée de bulles comme l'indique le titre.
    N'est-ce pas ?
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 822
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 822
    Points : 6 228
    Points
    6 228

    Par défaut

    Certes, mais à par l'exercice d'algo qui peut être intéressant, je ne vois vraiment pas l'utilité de trier une liste chaînée à postériori, surtout avec un tri à bulle, un tri par sélection peut être en recréant une autre liste ? (et encore c'est aussi stupide !)
    En fait je répondais surtout à la suggestion de Valetin03.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  8. #8
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Citation Envoyé par Trap D Voir le message
    Certes, mais à par l'exercice d'algo qui peut être intéressant, je ne vois vraiment pas l'utilité de trier une liste chaînée à postériori, surtout avec un tri à bulle, un tri par sélection peut être en recréant une autre liste ? (et encore c'est aussi stupide !)
    En fait je répondais surtout à la suggestion de Valetin03.
    La place en mémoire. Là où une application demande 1 gigaoctet par un tri "sur place", la tienne demandera 2 gigaoctets (1 pour la liste de départ et 1 pour le résultat).
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  9. #9
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 822
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 822
    Points : 6 228
    Points
    6 228

    Par défaut

    Ah bon, moi j'aurais déplacé les noeuds en changeant simplement les pointeurs.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  10. #10
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    2 744
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 2 744
    Points : 6 401
    Points
    6 401

    Par défaut

    Citation Envoyé par Trap D Voir le message
    Ah bon, moi j'aurais déplacé les noeuds en changeant simplement les pointeurs.
    Donc tu vois l'intérêt de trier une liste.
    Cette réponse vous plaît ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  11. #11
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 822
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 822
    Points : 6 228
    Points
    6 228

    Par défaut

    Bien sur, mais
    primo le tri par sélection en créant une nouvelle liste est plus simple (et ne double pas la taille mémoire)
    secundo trier une liste chaînée à postériori me semble stupide, elle devrait être triée au moment de la création.
    C'est tout.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  12. #12
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Vienne (Limousin)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2017
    Messages : 4
    Points : 14
    Points
    14

    Par défaut Correction

    La prof l'avez mis dans une annale sans nous donner la correction.

    Heureusement qu'on lui a signalé qu'on ne l'avais pas vu ensemble...

    Voila la solution

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void Tri_bulle() {           //si la liste est vide, rien à trier
            if(tete == null || tete.suivant == null)    return ;
    
            boolean trie = false;
            while(!trie) 
    { 
                             trie = true;
                             Cellule c = tete;                  
                             while(c.suivant!= null)
     {
                                        if (c.valeur > c.suivant.valeur) 
    {
                                                     int tmp_val=c.suivant.valeur;
                                                     c.suivant.valeur = c.valeur;
                                                     c.valeur=tmp_val;
                                                     trie = false; 
                                        }
                             c=c.suivant;
                             }
            } 
    }

  13. #13
    Membre éprouvé
    Profil pro
    Inscrit en
    avril 2004
    Messages
    660
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations forums :
    Inscription : avril 2004
    Messages : 660
    Points : 945
    Points
    945

    Par défaut Cette méthode de tri est très inefficace

    Cette méthode de tri est très inefficace (cf Numerical recipes)
    Quicksort et heapsort sont bien meilleurs.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

Discussions similaires

  1. Tri rapide de liste chainée
    Par A_B dans le forum C
    Réponses: 7
    Dernier message: 17/04/2007, 00h26
  2. probleme avec liste chainée
    Par isoman dans le forum C
    Réponses: 14
    Dernier message: 30/11/2006, 00h03
  3. probleme avec liste chainée
    Par Liiscar dans le forum java.util
    Réponses: 3
    Dernier message: 28/11/2006, 21h37
  4. [debutant] pb avec liste Chainée.
    Par FamiDoo dans le forum Débuter
    Réponses: 2
    Dernier message: 19/03/2006, 17h41
  5. Mal a la tete avec liste chainée d'objet
    Par Raton dans le forum C++
    Réponses: 23
    Dernier message: 03/08/2005, 23h13

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo