Tri à bulle avec liste chainée

Version imprimable

05/02/2018, 12h24
Shol4891

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.
05/02/2018, 14h58
Flodelarab

Bonjour :coucou:

Citation:

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 :ccool:
05/02/2018, 16h24
dourouc05

:salut:

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 ;).
05/02/2018, 20h37
valentin03

Bah, mets la liste en tableau, trie et remets en chaîne
07/02/2018, 20h35
Trap D

Ou alors insérer dans l'ordre au moment de la création ...
07/02/2018, 21h36
Flodelarab

Citation:

Envoyé par Trap D

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 ?
08/02/2018, 00h37
Trap D

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.
08/02/2018, 09h21
Flodelarab

Citation:

Envoyé par Trap D

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).
08/02/2018, 09h43
Trap D

Ah bon, moi j'aurais déplacé les noeuds en changeant simplement les pointeurs.
08/02/2018, 12h16
Flodelarab

Citation:

Envoyé par Trap D

Ah bon, moi j'aurais déplacé les noeuds en changeant simplement les pointeurs.

:lol: Donc tu vois l'intérêt de trier une liste.
08/02/2018, 15h09
Trap D

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.

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...:roll:

Voila la solution

Code:

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

14/02/2018, 12h23
Nebulix

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.