Trier des listes chaînées

si quelqu 'u peut nous eclairer sur :
le tri par selection des listes chainee
tri par insertion des listes chainee
:D :D :D :D

bonjour, merci au revoir, et surtout merci Google :-)

je tape "tri par selection" et hop : http://lwh.free.fr/pages/algo/tri/tri_selection.htm

trop dur :-(

ok j'ai vu de quoi tu parlais, mais il aurait fallu que tu mettes ton post du forum Java ici, parce qu'est du C...

Je recopie donc ici ton code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

// Tri selection //////////////// static Liste Tri_Selection_Liste(Liste l) { if (l == null) return null ;   // Recherche du minimum : attention au decalage d'un cran de l1 et l2 Liste l1 = l, l2 = null ; ; int min = l.elt ; while (l1.suivant != null) { if (l1.suivant.elt < min) { min = l1.suivant.elt ; l2 = l1 ; } l1 = l1.suivant ; }   // On supprime le minimum de la liste if (l2 == null) { l.suivant = Tri_Selection_Liste(l.suivant) ; return l ; } else { l1 = l2.suivant ; l2.suivant = l2.suivant.suivant ; l1.suivant = Tri_Selection_Liste(l) ; return l1 ; } }   // Tri insertion //////////////// static Liste Tri_Insertion_Liste(Liste l) { // On prend le premier element Liste l2 = l ; l = l.suivant ; l2.suivant = null ;   // On ajoute les elements suivants while (l != null) { if (l.elt < l2.elt) { Liste l1 = l ; l = l.suivant ; l1.suivant = l2 ; l2 = l1 ; } else { Liste l1 = l ; l = l.suivant ; l1.suivant = null ; Ajout_Trie_Liste(l2, l1) ; } } return l2 ; }   // Fonction d'ajout d'un element dans une liste triee static void Ajout_Trie_Liste(Liste l, Liste l1) { if (l.suivant == null) { l.suivant = l1 ; } else if (l1.elt < l.suivant.elt) { l1.suivant = l.suivant ; l.suivant = l1 ; } else Ajout_Trie_Liste(l.suivant, l1) ; }

---

C'est assez simple.

Ce que tu appelles "tri par insertion", c'est juste ajouter un élément entre 2 valeurs ..

chaque élément de la liste a une valeur...
à priori rangés par ordre croissant.

Quand tu veux insérer un nouvel élément, il parcoure la liste jusqu'à arriver à la bonne valeur (il s'arrête dès qu'il trouve une valeur supérieure ou égale à la valeur qu'il veut mettre) et là il insère l'élément dans la liste.

Quand à l'autre, il cherche à ajouter par "le début" .. il cherche le minimum, et il remplace le minimum par cette nouvelle valeur (ce qui entre nous est un petit peu stupide vu d'ici parce qu'à priori il a trié les valeurs par ordre croissant)....