Discussion :

[thecabbages]

Bonjours,
J'essaye de trouver un algo permettant des trier dans une liste simplement chainée a l'aide d'une pile.
pour cela, j'ai penser parcourir ma pile, et faire un swap lorsque l'element du dessus est plus grand que celui de dessous, et cela, n fois la taille de la pile. (un peu comme un tris dans une chaine normal).
voila comment je mi suis pris :

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
 while (j < pile->size) 
    {
      s1 = pile->top; //element du début
      s2 = pile->top->nxt; // second element
      while (i < pile->size) 
        {
          if (!tris_ascii(s1->nom, s2->nom))
           {
             // si s1->nom > s2->nom    on swap (non trouvé)
           }
 
          s1 = s1->nxt; //on parcour
          s2 = s2->nxt; //on parcour	  
          i++;
       }
     i = 1;
     j++;
   }

j'ai entendu des listes doublement chainée qui pourrait peut etre facilité la chose.
quelqu'un aurait une idée?

[huit_six]

Je comprends pas trop cette histoire de pile et de liste chaînée. Tes données sont dans une ile ou dans une liste chaînée ?
Le piles, ça ne me semble pas du tout adapté pour ce qui est du tri. ex :
13, 5, 7, 8, 3, 20, 8, 9
le sommet de la pile est à gauche, on veut classer par ordre croissant, le plus petit en haut de la pile donc.
Je rappelle que normalement, une pile a 2 opération principalement : pop qui dépile le dessus de la liste et push qui empile quelque chose sur la pile.
Pour inverser 20 et 8, il faut donc dépiler (pop) tout les nombres jusqu'à 8 compris, ré-empiler (push) 20, empiler 8 et ré-empiler tout le reste. Ça fait 14 opérations en tout, pas terrible comme algo.

avec des listes chaînées, c'est différent, on a :
13 -> 5 -> 7 -> 8 -> 3 -> 20 -> 8 -> 9

on parcourt la liste jusqu'au 20, on sauvegarde le pointeur sur le 8, on fait pointer 20 sur ce qui est pointé par 8 (9), on fait pointer 8 sur 20 et on fait pointer 3 sur 8. :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
13 -> 5 -> 7 -> 8 -> 3 -> 20 -> 8 -> 9
                              p ^
13 -> 5 -> 7 -> 8 -> 3 -> 20 -> 9
                         p -> 8 ^
13 -> 5 -> 7 -> 8 -> 3 -> 20 -> 9
                   p -> 8 ^
13 -> 5 -> 7 -> 8 -> 3 -> 8 -> 20 -> 9
                        p ^

Avec des listes chaînées, inverser deux valeurs revient à échanger des pointeurs.

Enfin, une liste doublement chaînée permet seulement d'améliorer le parcourt en sens inverse d'une liste. Ça complexifie (un peu hein !) l'algorithme d'interversion de deux valeurs.

[thecabbages]

Merci pour ta reponse, je vais travailler tous ca pour voir ce que sa donne.

[Pouet_forever]

Je pense que le plus simple à mettre en œuvre pour trier une liste chaînée est encore le tri par sélection. Après ce n'est peut-être pas le plus rapide (O(N²)) mais plus simple à mettre en œuvre que le tri à bulle