IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Tri à bulle avec liste chainée


Sujet :

Algorithmes et structures de données

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

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2017
    Messages : 8
    Points : 18
    Points
    18
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Responsable Qt & Livres


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

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

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    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 (tutoriels, FAQ, traductions) ou 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 actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    Février 2013
    Messages
    317
    Détails du profil
    Informations personnelles :
    Sexe : Homme

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

    Informations forums :
    Inscription : Février 2013
    Messages : 317
    Points : 233
    Points
    233
    Par défaut
    Bah, mets la liste en tableau, trie et remets en chaîne
    Savoir pour comprendre et vice versa.

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

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    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 sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    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 apporte quelque chose ? Cliquez sur en bas à droite du message.

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

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    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
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Vienne (Limousin)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2017
    Messages : 8
    Points : 18
    Points
    18
    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 expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    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 Collection et Stream
    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